Question

1)

where is given by the following table. Give the state diagram of this machine. 91 91 92 92 91 93 94 94 93 95 95 94 95

2) Give formal descriptions (5-tuples) for the DFAs shown in figure below:

3) Give the state diagrams of DFAs recognizing the following languages over ? = {0, 1}:

a) L_Æ

b) L_?

c) {e, 1001}

d) {e, 101, 1001}

e) {w : w has prefix 10}

f) {w : w does not contain the substring 011}

4) Give the state diagrams of DFAs recognizing the following languages over ? = {0, 1}:

a) {w: |w| ? 5}

b) {w : every odd position of w is a 1}

c) {w : w has an even number of occurrences of the substring 100}

d) {w : w contains at least two 0’s and at most three 1s’}

e) {w : w begins with prefix 010 and ends with suffix 101}

5)

6) Each of the following languages is the intersection of two simpler languages over the alphabet ? ={ a, b}. For each, construct the DFA’s for the simpler languages, then combine them using the construction of the closure proof presented in lecture (and page 46 of text):

a) {w : w starts with a and has at most one b}

b) {w : w has an odd number of a’s and ends in b}

c) {w : w has an even length and an odd number of a’s}

7) Show that a DFA M_k = (Q_k, ?_k, ?_k, q₀, F_k) exists that recognizes each L_k = {w: w ends in k 0’s}

8) Give the state diagrams of NFAs with the specified number of states recognizing the following languages over ? = {0, 1}:

a) {e, 010} with four states

b) {w : w contains exactly three 1s}with four states

c) {w: |w| ? 4} with five states

d) {w : every odd position of w is a 0} with two states

e) {w : w begins and ends with the same symbol} with five states

f) {w : w does not contain the substring 011} with four states

9)

Answer 1

The answer to the 1st question is as follows:

since the Dfa is given the start state is q3 and the final state is also q3.

The diagram is as follows:

d. 95 tu