```Homework #4

1.  Construct a DFA equivalent to the NFA defined by
({p,q,r,s}, {0,1}, delta, p, {s}), where delta is defined by
the chart below.

| 0   1
-+--------
p|p,q  p
q| r   r
r| s   -
s| s   s

2.  Construct a finite automata equivalent to the regular expression
(1 v 01 v 001)* (e v 0 v 00).

3.  Construct a regular expression for the state diagram shown below.

0           1
+---+        +-+
|   |        | |
v   |        v |
+===+   1    +-+
-->||A||------->|B|
+===+        +-+
^          | ^
|        0 | | 1
|          v |
|     0    +-+
+----------|C|
+-+

4.  Which of the following languages are regular sets?  Prove your answer.
a) L1 = {0^{2n} | n >= 1}
b) L2 = {0^p 1^q 0^{p+q} | m >= 1 and n >= 1}
c) L3 = {x x^R: x in (0 v 1)+}
d) L4 = The set of all strings in (0 v 1)+ that do not contain the
substring 010.

5.  Use the pumping lemma to prove that language L defined below is not
regular.

L = {ww^c:  w in {a,b}*}, where w^c stands for w with each occurrence of a
replaced by b, and vice versa.

6.  Are the following statements true or false?  Explain your answer in each
case.

a) Every subset of a regular language is regular.
b) If L is regular, then so is {xy:  x in L and y not in L}.
c) If L is a regular language, then so is {w: w in L and w^R in L}.

7.  This problem is optional.

Simulate your constructed DFA from problem 1 using the DFA simulator
available at http://ranger.uta.edu/~cook/tcs/fsm/Simulator.html
Turn in a picture of the constructed DFA.  You will need a browser capable
of running Java applets to complete this homework problem.
```