By induction then, the result holds for all strings.
4. Since abaabaaabaa can be decomposed into strings ab, aa, baa, ab, aa, each
of which is in L, the string is in L * . Similarly, baaaaabaa is in L * . However,
there is no possible decomposition for baaaaabaaaab, so this string is not in
L * . The strings aaaabaaaa and baaaaabaa are in L 4 .
5.
.
11. (d) We first generate three a's, then add an arbitrary number of a’s and b’s
anywhere.
The first production generates three a’s. The second can generate any
number of a’s and b’s in any position. This shows that the grammar can
generate any string w ∈ {a, b} * as long as n a (w) ≥ 3.
12.
from which we see that
13.
, since no terminal string can be derived with these productions.
14. (a) Generate an equal number of a’s and b’s, then one or more b’s as
needed.