To show this, assume that the language is linear and apply Theorem 8.2 to
the string
Inequality (8.5) shows that in this case the strings u, v, y, z must all consist
entirely of a's. If we pump this string once, we get a m+k b 2m a m+l , with either k ≥ 1
or l ≥1, a result that is not in L. This contradiction of Theorem 8.2 proves that the
language is not linear.
This example answers the general question raised on the relation between the
families of context-free and linear languages. The family of linear languages is a
proper subset of the family of context-free languages.
EXERCISES
1. Show that the language
is not context-free.
2. Show that the language L = {a n : n is a prime number} is not context-free.
3. Show that
is not a context-free language.
4. Show that
is not context-free.
5. Is the language L = {a n b m : n = 2 m } context-free?
6. Show that the language L = {a n
2 : n ≥ 0} is not context-free.
7. Show that the following languages on Σ = {a, b, c} are not context-free.
(a) L = {a n b j : n ≤ j 2 }.
(b) L = {a n b j : n ≥ (j - 1) 3 }.
(c) L = {a n b j c k : k = jn}.
(d) L = {a n b j c k : k>n, k >j}.