and so on, completing the proof of the theorem.
We have given the pumping lemma only for infinite languages. Finite
languages, although always regular, cannot be pumped since pumping
automatically creates an infinite set. The theorem does hold for finite languages,
but it is vacuous. The m in the pumping lemma is to be taken larger than the
longest string, so that no string can be pumped.
The pumping lemma, like the pigeonhole argument in Example 4.6, is used
to show that certain languages are not regular. The demonstration is always by
contradiction. There is nothing in the pumping lemma, as we have stated it here,
that can be used for proving that a language is regular. Even if we could show
(and this is normally quite difficult) that any pumped string must be in the
original language, there is nothing in the statementof Theorem 4.8 that allows us
to conclude from this that the language is regular.
Example 4.7
Use the pumping lemma to show that L = {a n b n : n ≥ 0} is not regular. Assume
that L is regular, so that the pumping lemma must hold. We do not know the
value of m, but whatever it is, we can always choose n = m. Therefore, the
substring y must consist entirely of a's. Suppose |y| = k. Then the string obtained
by using i = 0 in Equation (4.2) is
and is clearly not in L. This contradicts the pumping lemma and thereby
indicates that the assumption that L is regular must be false.
In applying the pumping lemma, we must keep in mind what the theorem
says. We are guaranteed the existence of an m as well as the decomposition xyz,
but we do not know what they are. We cannot claim that we have reached a
contradiction just because the pumping lemma is violated for some specific
We have given the pumping lemma only for infinite languages. Finite
languages, although always regular, cannot be pumped since pumping
automatically creates an infinite set. The theorem does hold for finite languages,
but it is vacuous. The m in the pumping lemma is to be taken larger than the
longest string, so that no string can be pumped.
The pumping lemma, like the pigeonhole argument in Example 4.6, is used
to show that certain languages are not regular. The demonstration is always by
contradiction. There is nothing in the pumping lemma, as we have stated it here,
that can be used for proving that a language is regular. Even if we could show
(and this is normally quite difficult) that any pumped string must be in the
original language, there is nothing in the statementof Theorem 4.8 that allows us
to conclude from this that the language is regular.
Example 4.7
Use the pumping lemma to show that L = {a n b n : n ≥ 0} is not regular. Assume
that L is regular, so that the pumping lemma must hold. We do not know the
value of m, but whatever it is, we can always choose n = m. Therefore, the
substring y must consist entirely of a's. Suppose |y| = k. Then the string obtained
by using i = 0 in Equation (4.2) is
and is clearly not in L. This contradicts the pumping lemma and thereby
indicates that the assumption that L is regular must be false.
In applying the pumping lemma, we must keep in mind what the theorem
says. We are guaranteed the existence of an m as well as the decomposition xyz,
but we do not know what they are. We cannot claim that we have reached a
contradiction just because the pumping lemma is violated for some specific