1(a)

Let L = {w {0, 1} |w starts with a 0 and has even length}. Starting with DFAs for two simpler languages, use the intersection construction to give a DFA that recognizes L. 5.

(b) Give an NFA with four states that recognizes L1 = {w {0, 1} |one of the last three symbols in w is a 1}.

(c) Give an NFA with three states that recognizes the language L2 = 0 1 0 1 2

(d) Convert the NFA given in Figure 1.27 of the textbook into a DFA. Show only the reachable states of the DFA.

0,1 0,1 93 FIGURE1.27 The nondeterministic finite automaton N