Consider the language L over the alphabet {0, 1} described as follows:

L = {w | w has an odd number of 0s or it has 010 as a substring}.

1. Describe L as the union of two simpler languages.

2. Provide DFAs that recognize the simpler languages.

3. Use the two DFAs you have provided and the construction of Theorem 1.25 to obtain an DFA

recognizing L.

4. Is the resulting DFA as simple as possible or can some states in it be collapsed?

Note that following the steps in the problem is important. For example, you will not get credit for

presenting a DFA directly for the language L.

Part 2:

1. Use the DFAs for the two simpler languages that you have identified in Problem 3 and the

construction in Theorem 1.45 to obtain an NFA for the language L described in that problem.

2. Use the construction (to be) described in class to obtain a DFA from the NFA you have

provided in the previous part. You must show your work to get credit for this part; simply

presenting a DFA for the language will get no credit. Also note that you must use the

construction from class that works with reachable states for this part. The construction in

the book, uses the powerset of the set of states in the NFA as the states of the DFA, is not

practical, certainly not for doing problems by hand and on paper.

3. Contrast the two DFAs that you have developed for the language L, one in this problem and

the other in Problem 3. If they are the same, present a mapping between the states in the

two that shows they are the same. If they are different, the DFA that has more states must

have some states that are equivalent. Identify these states.