Scribd
Upload
587 views4 pages

Problem

The document provides a problem to design state diagrams for NFAs with a specified number of states that recognize various languages over the alphabet {0,1}. It then shows the step-by-step solution for drawing the state diagrams of NFAs that recognize 8 different languages, including languages that end with 00, contain certain substrings, accept strings with 0s and 1s followed by a 0, and more.

Uploaded by

Md Furkan Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
587 views4 pages

Problem

The document provides a problem to design state diagrams for NFAs with a specified number of states that recognize various languages over the alphabet {0,1}. It then shows the step-by-step solution for drawing the state diagrams of NFAs that recognize 8 different languages, including languages that end with 00, contain certain substrings, accept strings with 0s and 1s followed by a 0, and more.

Uploaded by

Md Furkan Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Problem

Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.

Aa. The language {w| w ends with 00} with three states

b. The language of Exercise 1.6c with five states

c. The language of Exercise 1.6l with six states

d. The language {0} with two states

e. The language 0*1*0+ with three states

Af. The language 1*(001+)* with three states

g. The language { } with one state

h. The language 0* with one state

Step-by-step solution

Step 1 of 8

a.

Consider the Language with three states over the alphabet . The language states that the Finite automata should
consist of three states that accept the strings over the alphabet and ends with 00. Let M be the NFA that recognizes . The state diagram
of M is as follows:

Comment

Step 2 of 8

b.

Consider the Language

with five states over the alphabet . The language states that
the Finite automata should consist of five states that accept the strings over the alphabet and contains the substring 0101. Let M be the
NFA that recognizes . The state diagram of M is as follows:

Comment
Step 3 of 8

c.

Consider the Language

with 6 states over the alphabet . Let M be the NFA that recognizes
. Divide L into 2 languages and .

Let be the NFAs recognizes respectively.

State diagram of is as follows:

The state diagram of is as follows:

Now

The sate diagram of M that recognizes L is as follows:

Comments (2)

Step 4 of 8

d.

Consider the Language with 2 states over the alphabet . Let M be the NFA that recognizes . The state
diagram of M is as follows:

Comment

Step 5 of 8

e.

Consider the Language with 3 states over the alphabet . The language states that the finite automata
accept all the strings containing any number of zeroes and ones followed by at least one zero. Let M be the NFA that recognizes . The state
diagram of M is as follows:

f.
Comments (21)

Step 6 of 8

Consider the Language that accepts the strings of the form with 3 states over the alphabet . Let M be the NFA that
recognizes . The state diagram of M is as follows:

Comment

Step 7 of 8

g.

Consider the Language with one state over the alphabet . The language states that
the finite automata accept a null string. Let M be the NFA that recognizes . The state diagram of M is as follows:

Comment

Step 8 of 8

h.

Consider the Language L that accepts the strings of the form with one state over the alphabet . Let M be the NFA that recognizes L.
The state diagram of M is as follows:

Comment

You might also like