now chooses a y (by necessity consisting of all a’s) of length k < m, we pump i
times to generate a string with m! +(i − 1) k a’s. We can get a contradiction of the
pumping lemma if we can pick i such that
This is always possible since
and k ≤ m. The right side is therefore an integer, and we have succeeded in
violating the conditions of the pumping lemma.
However, there is a much more elegant way of solving this problem. Suppose
L were regular. Then, by Theorem 4.1, and the language
would also be regular. But L 1 = {a n b n : n ≥ 0}, which we have already classified
as nonregular. Consequently, L cannot be regular.
The pumping lemma is difficult to understand and it is easy to go astray
when applying it. Here are some common pitfalls. Watch out for them.
One mistake is to try using the pumping lemma to show that a language is
regular. Even if you can show that no string in a language L can ever be pumped
out, you cannot conclude that L is regular. The pumping lemma can only be used
to prove that a language is not regular.
Another mistake is to start (usually inadvertently) with a string not in L. For
example, suppose we try to show that
is not regular. An argument that starts with “Given m, let w = a m …,” is incorrect
since m is not necessarily prime. To avoid this pitfall, we need to start with
something like “Given m, let w = a M , where M is a prime number larger than m.”
Finally, perhaps the most common mistake is to make some assumptions
about the decomposition xyz. The only thing we can say about the decomposition
is what the pumping lemma tells us, namely, that y is not empty and that |xy| ≤ m;
that is, that y must be within m symbols of the left end of the string. Anything