be some k for which this happens. The npda chooses the k
nondeterministically.
12. Use the pumping lemma for linear languages. With a given m, choose w =
a m b 2m a m . Now v and y are entirely made of a’s, so w is easily pumped out
of the language.
15. The language is not linear. With the pumping lemma, use
where (…( and )…) stand for m left or right parentheses, respectively. If |u|
≥ 1, we can easily pump so that for some prefix v, n ( (v) < n ) (v) which
results in an improper expression. Similar arguments hold for other
decompositions.
20. Use w = a pq , where p and q are primes such that p > m and q > m. If |vy| =
k, then
If we choose i = pq, then
which is not in the language.
Section 8.2
1. The complement is context-free. The complement involves two cases: n a (w)
≠ n b (w) and n a (w) ≠ n c (w). These in turn can be broken into n a (w) > n b
(w), n a (w) > n c (w), n a (w) < n b (w), and n a (w) < n c (w). Each of these is
context-free as can be shown by construction of a CFG. The full language is
then the union of these four cases and by closure under union is context-free.
5. Given a context-free grammar G, construct a context-free grammar by
replacing every production A → x by A → x R . We can then show by an
induction on the number of steps in a derivation that if w is a sentential form
for G, then w R is a sentential form for .
nondeterministically.
12. Use the pumping lemma for linear languages. With a given m, choose w =
a m b 2m a m . Now v and y are entirely made of a’s, so w is easily pumped out
of the language.
15. The language is not linear. With the pumping lemma, use
where (…( and )…) stand for m left or right parentheses, respectively. If |u|
≥ 1, we can easily pump so that for some prefix v, n ( (v) < n ) (v) which
results in an improper expression. Similar arguments hold for other
decompositions.
20. Use w = a pq , where p and q are primes such that p > m and q > m. If |vy| =
k, then
If we choose i = pq, then
which is not in the language.
Section 8.2
1. The complement is context-free. The complement involves two cases: n a (w)
≠ n b (w) and n a (w) ≠ n c (w). These in turn can be broken into n a (w) > n b
(w), n a (w) > n c (w), n a (w) < n b (w), and n a (w) < n c (w). Each of these is
context-free as can be shown by construction of a CFG. The full language is
then the union of these four cases and by closure under union is context-free.
5. Given a context-free grammar G, construct a context-free grammar by
replacing every production A → x by A → x R . We can then show by an
induction on the number of steps in a derivation that if w is a sentential form
for G, then w R is a sentential form for .