3.3 Chapter 1, Sections 1.3-1.4

Complete the following problems:

1. (0.25) Convert the DFA below into a regular expression. I suggest ripping in the order q2, q1, q0.

   • Q = {q0, q1, q2}

   • Σ = {0,1}

   • δ = {(q0,1,q2) (q0,0,q1) (q1,1,q0) (q1,0,q2) (q2,1,q1) (q2,0,q0)}

   • q0 = q0

   • F = {q2}

2. (0.25) Consider the language L1 = {w | w is of the form (a∪b)(aa*b ∪ a)*} for the alphabet {a,b}.

   1. (0.02) Give two examples of strings that are in L1.

   2. (0.02) Give two examples of strings that are not in L1.

   3. (0.21) Convert the regular expression into an NFA. You may only draw the diagram if that is easier for you.

3. (0.25) Do problem 1.29(b) from the textbook. This is the one about applying the pumping lemma to www.

4. (0.25) Prove or disprove: L2 = {a^n b^3n | n >= 0 } is regular for the alphabet {a,b}.