1. Construct an dfa that accepts { w an element of {a, b}^* | n_a(w) = 2}

2. Construct an nfa that accepts {w is an element of {a, b}*| n_a (w) =2 OR n_b = 2}.

3. Write a regular expression which represents the language { w is an element of {a, b}^* | w can be written x₁, x₂, x₃, ...x_m, m >= 0 , where each x_i is either ab or ba}.

4. In problem 1 change n_a(w) =2 to n_a(w) >= 2 .

5. In problem 3 change n >= 0 to n >= 1.

6. (a) Finf an nfa that accepts the language in #3 above.

(b) Find a dfa for the samr language.

7. (a) nfa for (a+b)^* (b+a²)^*

(b) dfa for the same language [ Long, EC problem].

8. Find a dfa that accepts L = {w an element of {a, b}* | n_a (w) is even, n_b (w) is odd}.

9. Show a right Linear grammer for the languageof nfa in problem #7 above.

10. Construct an NFA for :

S --> abA

A---> baB

B---> aA / bb