(d) The answer is easier to see if you notice that
This leads to the easy solution
15. (b) The problem is simplified if you break it into two cases, |w| mod 3 = 1
and |w| mod 3 = 2. The first is covered by
the second by
The two can be combined into a single grammar by
18. (a) We can use the trick and results of Example 1.13. Let L 1 be the
language in Example 1.13 and modify that grammar so that the start
symbol is S 1 . Consider then a string w ∈ L. If this string starts with an
a, then it has the form w = aw 1 , where w 1 ∈ L 1 . This situation can be
taken care of by S → aS 1 . If it starts with a b, it can be derived by S →
S 1 S.
23. The first grammar can derive
, but the second grammar
cannot derive this string.
Section 1.3
1.