**CSE
3502, Homework 2: Finite State Automata
due Tuesday 2/6/17**

*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, q_{0}, *F*). We
create a DFA *M'* by swapping the *accept*
and *reject *states of *M*, so that M' = (*Q*, S, d, q_{0}, *Q*-*F*).
Prove that *L**(**M') *is the *complement* of *L**(M)*; that is, ** L**(

**(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(L_{1}
U L_{2}) = Rev(L_{1})
U Rev(L_{2})

Rev(L_{1} ^{o} L_{2})
= Rev(L_{2}) ^{o} Rev(L_{1})

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

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