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.