13. (a) If S derives L, then S 1 → SS derives L 2 .
16. It is normally not possible to use a grammar for L directly to get a grammar
for , so we need another, hopefully recursive description for . This is a
little hard to see here. One obvious subset of contains the strings of odd
length, but this is not all.
Suppose we have an even-length string that is not of the form ww R .
Working from the center to the left and to the right simultaneously, compare
corresponding symbols. While some part around the center can be of the
form ww R , at some point we get an a on the left and a b in the
corresponding place on the right, or vice versa. The string must therefore be
of the form uaww R bv or ubww R av with |u| = |v|. Once we see this, we can
then construct grammars for these types of strings. One solution is
The first two productions generate the u and v, the third the two disagreeing
symbols, and the last the innermost palindrome.
20. The only possible derivations start with
But this sentential form has the suffix aba so it cannot possibly lead to the
sentence aabbabba.
23.
Section 5.2
2. A solution is