else makes the argument invalid. A typical mistake in trying to prove that the
language in Equation (4.3) is not regular is to say that y = a k , with k odd. Then of
course w = xz is an even-length string and thus not in L. But the assumption on k
is not permitted and the proof is wrong.
But even if you master the technical difficulties of the pumping lemma, it
may still be hard to see exactly how to use it. The pumping lemma is like a game
with complicated rules. Knowledge of the rules is essential, but that alone is not
enough to play a good game. You also need a good strategy to win. If you can
apply the pumping lemma correctly to some of the more difficult cases in this
book, you are to be congratulated.
EXERCISES
1. Prove the following version of the pumping lemma. If L is regular, then there
is an m such that, every w ∈ L of length greater than m can be decomposed
as
w = xyz,
with |yz| ≤ m and |y| ≥ 1, such that xy i z is in L for all i.
2. Prove the following generalization of the pumping lemma, which includes
Theorem 4.8 as well as Exercise 1 as special cases.
If L is regular, then there exists an m, such that the following holds for every
sufficiently long w ∈ L and every one of its decompositions w = u 1 υu 2 , with
u 1 ,u 2 ∈ , |υ| ≤ m. The middle string υ can be written as υ = xyz, with |xy| ≤
m, |y| ≥ 1, such that u 1 xy i zu 2 ∈ L for all i = 0,1, 2,….
3. Show that the language L = {w : n a (w) = n b (w) } is not regular. Is
regular?
4. Prove that the following languages are not regular.
(a) L = {a n b l a k : k ≥ n + l}.
(b) L = {a n b l a k : k ≠ n + l}.
(c) L = {a n b l a k : n = l or l ≠ k}.