1. Construct a dfa that accepts the language generated by the grammar
S → abA,
A → baB,
B → aA|bb.
2. Find a regular grammar that generates the language L (aa* (ab+ a)*).
3. Construct a left-linear grammar for the language in Exercise 1.
4. Construct right-and left-linear grammars for the language
L = {a n b m : n ≥ 2, m ≥ 3}.
5. Adapt the construction in Theorem 3.4 to find a left-linear grammar for the
language accepted by the nfa below.
6. Construct a right-linear grammar for the language L ((aab*ab)*).
7. Find a regular grammar that generates the language on Σ = {a, b} consisting
of all strings with no more than three a's.
8. In Theorem 3.5, prove that L( ) = (L(G)) R .
9. Suggest a construction by which a left-linear grammar can be obtained from
an nfa directly.
10. Find a left-linear grammar for the language in Exercise 6.
11. Find a regular grammar for the language L = {a n b m : n + m is even}.
12. Find a regular grammar that generates the language
13. Find regular grammars for the following languages on { a, b}.