AUTOMATA THEORY

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

2. Each of the following languages are composed of two simpler languages over the alphabet = {a, b, c}. For both, construct the DFAs for the simpler languages, then combine them using the construction of the closure proof presented in lecture (and page 46 of text):

1. {w : w starts with b and has at most one a}
2. {w : w has an even number of as or ends in c}

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

1. Lwith one state
2. L_ewith one state
3. {w : w contains only 0s}with one state