1. Construct a dfa that accepts the language generated by the grammar S → abA, A → baB, B → aA|bb.
1. Construct a dfa that accepts the language generated by the grammar
S → abA,
A → baB,
B → aA|bb.
2. Construct a dfa that accepts the language generated by the grammar
S → abS|A,
A → baB,
B → aA|bb.
3. Find a regular grammar that generates the language L(aa∗ (ab + a)
∗).
4. Construct a left-linear grammar for the language in Exercise 1.
5. Construct right- and left-linear grammars for the language
L = {anb
m : n ≥ 3, m ≥ 2} .
6. Construct a right-linear grammar for the language L((aaab∗ab)
∗).
7. Find a regular grammar that generates the language on Σ = {a, b} consisting
of all strings with no more than two a’s.
8. In Theorem 3.5, prove that L
G
= (L(G))R.
9. Suggest a construction by which a left-linear grammar can be obtained from
an nfa directly.
10. Use the construction suggested by the above exercises to construct a leftlinear grammar for the nfa below.
q0 q1 q2
1
0
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
