(h) .
(i)
.
*15. Find grammars for the following languages on ∑ = {a}.
(a) L = {w : |w| mod 3 = 0}.
(b) L = {w : |w| mod 3 > 0}.
(c) L = {w : |w| mod 3 ≠ |w| mod 2}.
(d) L = {w : |w| mod 3 ≥ |w| mod 2}.
16. Find a grammar that generates the language
Give a complete justification for your answer.
17. Give a verbal description of the language generated by
18. Using the notation of Example 1.13, find grammars for the languages below.
Assume ∑ = {a, b}.
(a) L = {w : n a (w)= n b (w) + 1}.
(b) L = {w : n a (w) > n b (w)}.
*(c) L = {w : n a (w) = 2n b (w)}.
(d) L = {w ∈ {a, b}* : |n a (w) − n b (w)| = 1}.
19. Repeat the previous exercise with ∑ = {a, b, c}.
20. Complete the arguments in Example 1.14, showing that L (G 1 ) does in fact
generate the given language.
21. Are the two grammars with respective productions
(i)
.
*15. Find grammars for the following languages on ∑ = {a}.
(a) L = {w : |w| mod 3 = 0}.
(b) L = {w : |w| mod 3 > 0}.
(c) L = {w : |w| mod 3 ≠ |w| mod 2}.
(d) L = {w : |w| mod 3 ≥ |w| mod 2}.
16. Find a grammar that generates the language
Give a complete justification for your answer.
17. Give a verbal description of the language generated by
18. Using the notation of Example 1.13, find grammars for the languages below.
Assume ∑ = {a, b}.
(a) L = {w : n a (w)= n b (w) + 1}.
(b) L = {w : n a (w) > n b (w)}.
*(c) L = {w : n a (w) = 2n b (w)}.
(d) L = {w ∈ {a, b}* : |n a (w) − n b (w)| = 1}.
19. Repeat the previous exercise with ∑ = {a, b, c}.
20. Complete the arguments in Example 1.14, showing that L (G 1 ) does in fact
generate the given language.
21. Are the two grammars with respective productions