Hello I am really desperate because i can't figure out this problem I have tried this problem multiple times and I just don't understand the theorem or the problem.I need help with 1.10 part B but to answer 1.10 part B you would need the question for 1.6 j and the theorem. this is the response that I get when it is incorrect. "Incorrect.the empty string is an example".  question for 1.10 that I need help with: 1.10 use the construction in the proof of theorem 1.49 to give the state diagrams of NFAs recognizing the star of the language described in  b) exercise 1.6j Question for 1.6j 1.6 Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}. j. {w | w contains at least two 0s and at most one 1}

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

Hello I am really desperate because i can't figure out this problem I have tried this problem multiple times and I just don't understand the theorem or the problem.I need help with 1.10 part B but to answer 1.10 part B you would need the question for 1.6 j and the theorem.

this is the response that I get when it is incorrect. "Incorrect.the empty string is an example". 

question for 1.10 that I need help with:
1.10 use the construction in the proof of theorem 1.49 to give the state diagrams of NFAs recognizing the star of the language described in 

b) exercise 1.6j

Question for 1.6j

1.6 Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.

j. {w | w contains at least two 0s and at most one 1}

THEOREM
1.49
The class of regular languages is closed under the star operation.
PROOF IDEA We have a regular language A₁ and want to prove that A₁ also
is regular. We take an NFA N₁ for A₁ and modify it to recognize At, as shown in
the following figure. The resulting NFA N will accept its input whenever it can
be broken into several pieces and N₁ accepts each piece.
We can construct N like N₁ with additional e arrows returning to the start
state from the accept states. This way, when processing gets to the end of a piece
that N₁ accepts, the machine N has the option of jumping back to the start state
to try to read another piece that N₁ accepts. In addition, we must modify N
so that it accepts e, which always is a member of A. One (slightly bad) idea is
simply to add the start state to the set of accept states. This approach certainly
adds e to the recognized language, but it may also add other, undesired strings.
Exercise 1.15 asks for an example of the failure of this idea. The way to fix it is
to add a new start state, which also is an accept state, and which has an e arrow
to the old start state. This solution has the desired effect of addinge to the
language without adding anything else.
N₁
O
ORANG DOODPO UNA ROAGO DO O ONASIN 300 000
O
N
E
O
O
E
Transcribed Image Text:THEOREM 1.49 The class of regular languages is closed under the star operation. PROOF IDEA We have a regular language A₁ and want to prove that A₁ also is regular. We take an NFA N₁ for A₁ and modify it to recognize At, as shown in the following figure. The resulting NFA N will accept its input whenever it can be broken into several pieces and N₁ accepts each piece. We can construct N like N₁ with additional e arrows returning to the start state from the accept states. This way, when processing gets to the end of a piece that N₁ accepts, the machine N has the option of jumping back to the start state to try to read another piece that N₁ accepts. In addition, we must modify N so that it accepts e, which always is a member of A. One (slightly bad) idea is simply to add the start state to the set of accept states. This approach certainly adds e to the recognized language, but it may also add other, undesired strings. Exercise 1.15 asks for an example of the failure of this idea. The way to fix it is to add a new start state, which also is an accept state, and which has an e arrow to the old start state. This solution has the desired effect of addinge to the language without adding anything else. N₁ O ORANG DOODPO UNA ROAGO DO O ONASIN 300 000 O N E O O E
Incorrect The empty string is an example.
Submit
qo
93
0
0
4
q6
0
92
q5
Transcribed Image Text:Incorrect The empty string is an example. Submit qo 93 0 0 4 q6 0 92 q5
Expert Solution
steps

Step by step

Solved in 3 steps with 1 images

Blurred answer
Knowledge Booster
Processes of 3D Graphics
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education