796
Modeling Arithmetic, Computation, and Languages
3. Describe L(G) for the grammar G = (V, V T , S, P) where V = 50, 1, A, B, S6, V T = 50, 16, and P consists of
S S 0
A S 1B
B S 0A
S S 0A
B S 0
What type of grammar is this?
4. Describe L(G) for the grammar G = (V, V T , S, P) where V = 50, 1, A, S6, V T = 50, 16, and P consists of
S S 0S
A S 1A
S S 11A
A S 1
What type of grammar is this?
5. Find a regular grammar that generates the language of Exercise 1.
6. Find a regular grammar that generates the language of Exercise 2.
7. Find a regular grammar that generates the language of Exercise 3.
8. Find a regular grammar that generates the language of Exercise 4.
9. Describe L(G) for the grammar G = (V, V T , S, P) where V = 5a, b, A, B, S6, V T = 5a, b6, and P consists of
S S aA
S S l
A S bS
10. Describe L(G) for the grammar G = (V, V T , S, P) where V = 50, 1, A, S6, V T = 50, 16, and P consists of
S S 0
S S ASA
A S 1
11. Describe L(G) for the grammar G = (V, V T , S, P) where V = 5a, b, A, B, S6, V T = 5a, b6, and P consists of
S S AB
AB S AAB
A S a
AB S ABB
B S b
What type of grammar is G? Find a regular grammar G′ that generates L(G).
12. Describe L(G) for the grammar G = (V, V T , S, P) where V = 5a, b, c, A, B, C, R, T, S6, V T = 5a, b, c6,
and P consists of
S S ARBT
T S cT
R S ARB
T S c
RB S ACBB
A S a
CB S BC
B S b
CT S cT
What type of grammar is G? Find a context-free grammar G′ that generates L(G). Explain why it is not
possible to find a regular grammar that generates L(G).