CSE 3502, Homework 2: Finite State Automata
due Tuesday 2/6/17
at the beginning of class

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


Note: in this homework, we are looking for proper proofs, with steps, making use of definitions and building on what's given. Please refer to the book for examples of proper proofs.

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 {w: w contains an even number of 0's, or contains exactly two 1's}. 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. Compliment

(a) Let M be some DFA (Q, S, d, q0, F). We create a DFA M' by swapping the accept and reject states of M, so that M' = (Q, S, d, q0, Q-F). Prove that L(M') is the complement of L(M); that is, L(M') = S*- 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)? Please prove that it is not, by finding a counterexample.

Problem 3. Reversal

Given a language L, we define Rev(L), the reverse of L as {reverse(w), for all w in L} (for example, Rev({"abc", "cb"}) is {"cba", "bc"}). Prove by induction on the structure of regular expressions that if L is regular (meaning, it can be represented by a regular expression), then Rev(L) is also regular.


In your proof, you can make use of the following facts about languages without having to prove them:


Rev(L1 U L2) = Rev(L1) U Rev(L2)

Rev(L1 o L2) = Rev(L2) o Rev(L1)

Rev(L*) = (Rev(L))*


Hint: start by formulating very carefully what exactly is the claim that you will be proving about all regular expressions.