1.  (15 points) Draw the DFA that is described by the formal definition:

({q0, q1, q2, q3, q4, q5}, {0, 1}, 6, q0, {q0, q1, q3})

with 6 given by the table

(a)  Draw the state diagram of your DFA in flap.js, and include it as part of your submission.

(b)  Describe the language recognized by this DFA.

Solution:

Starts and ends with the same character (empty string included.) L(ε∪1∪0∪1Σ* 1∪0Σ* 0)

(c) Is it possible to construct a DFA that recognizes the same language with fewer states?  If not, explain why not. If so, then draw it using flap.js.

Solution:

State q5 is not needed since it is impossible to get to from the starting vertex, so you can remove it and the resulting DFA will recognize the same language.

2.  (10 points)

Consider the DFA, M , whose state diagram is given by:

a)  Draw out the computation of this machine on the input 00010101. (You can handdraw this. You can draw it as a vertical chain of states going down like we did in class or you can draw it horizontally.)

b)  Describe the language L(M).

Solution:

Starts with 00 and ends with 00 (and has 4 or more characters.), L(00Σ* 00).

c) If w ∈ L(M), will the string obtained by flipping bits in w (changing 0 to 1 and 1 to 0) also be in L(M)? Explain your answer.

Solution:

No, because if w ∈ L(M) then it starts with 00 and ends with 00 and flipping the bits of w will result in a string that starts with 11 and ends with 11 which is not in the language.

d) If w ∈ L(M), will the string wR  (the reverse of w) also be in L(M)? Explain your answer

Solution:

Yes, because if w ∈ L(M) then w starts with 00 and ends with 00 and if you reverse w then it still starts and ends with 00 so the result is still in the language.

e)  Describe in your own words the “role” of each of the states.

Solution:

. q0 Start state, haven’t seen any character yet.

. q1 Seen that the first character of the string is 0 so far.

. q2 Seen that the first character of the string is 1 or the first two characters of the string

are 01 (and any string starting with 1 or 01 will get trapped there.)

. q3 Seen that the first two characters of the string are 00 and the string is 00 or the

string starts with 00 and ends with 1.

. q4 Seen that the first two characters of the string are 00 and the string ends in 0 so far. . q5 Seen that the first two characters of the string are 00 and the string ends in 00.

f) Write a regular expression that describes L(M).  (please explain your reasoning.)

Solution:

L(00Σ* 00) it can start with 00 then there can be any string in the middle and it must end

in 00.

3.  (12 points) Consider the DFAs M1  (on the left) and M2  (on the right):

(a) If we use the general constructions discussed in class and in the book for building a DFA whose

language is

L(M1 ) ∪ L(M2 )

how many states would be in this DFA? Briefly justify your calculation.

Solution:

According to the construction, the set of states for the new machine is Q1 × Q2 which means that there are (3)(4) = 12 possible states. As you can see, not all states are reach- able from the start state so we can reduce that number without changing the language of the DFA.

(b)  Draw the state diagram that results from this construction and remove any unreachable states.

How many states are left?

Solution:

8 states are left.

(c)  Describe the language L(M1 ) ∪ L(M2 ) in set builder notation or as a regular expression.

Solution:

The language of M1  is the set of all binary strings that end with 11 and the language of M2  is the set of binary strings that start with 00. So the language L(M1 ) ∪ L(M2 ) is the set of all strings that start with 00 or end with 11.

(d) Is there any way to build a machine that recognizes the same language (L(M1 ) ∪ L(M2 )) but uses fewer states?  (if s, you can either draw the result or describe in words how to construct it, if not, explain why not.)

Solution:  Yes, the upper right triangle (in my picture) can all be collapsed into one accept state that sends 0 and 1 to itself.

4.  (16 points)

Consider the two NFAs N1  and N2 .