CSE 237, Homework 2 (DFAs)
due 9/20/17 at the beginning of class

Please hand in the homework ON PAPER, either handwritten or printed.

Problem 1.

(a)      Let L be all strings over {0,1} that contain a pair of 1ís separated by an odd number of symbols.Draw the diagram of an NFA with 4 states that accepts L.


(b)      Let L be the language in exercise 1.6L . Draw the diagram of an NFA with 6 states that accepts L.


Hint: To "debug" your NFA, look for strings it accepts but should not, or strings it does not accept but should.

Problem 2. Single-state NFAs

(a)   Describe how to convert any NFA to an equivalent one that has a single final state. Use a picture, but also provide a formal description.


(b) Prove that your conversion works correctly, i.e. that the new single-state NFA is equivalent to the original one.


Note: NFAs are equivalent if every string accepted by the first is also accepted by the second one and vice versa.

Problem 3. Complement

(a)   Let M be some DFA (Q, Sigma, delta,q0,F). We create a DFA M' by swapping the accept and reject states of M, so that M' = (Q, Sigma, delta,q0,Q-F). Prove that L(M') is the complement of L(M); that is, L(M') = Sigma*- L(M).


(b) Suppose that in (a) above M were not a DFA but an NFA. Is it still true that, if we create M' as above, then L(M') is the complement of L(M)? Prove that it is not, by finding a counterexample.


(c) CLAIM: for any regular language L, its complement is also regular.Prove this claim, by making use of what you proved in part (a), as well as the Regular Language Theorem. (This should be a short proof)


†† Note: in this homework, we are looking for proper proofs, with steps, making use of definitions and building on whatís given.