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.