with n ≠ m. But since M accepts a n b n we must have
From this we can conclude that
This contradicts the original assumption that M accepts a m b n only if n = m, and
leadsusto conclude that L cannot be regular.
In this argument, the pigeonhole principle is just a way of stating
unambiguously what we mean when we say that a finite automaton has a limited
memory. To accept all a n b n , an automaton would have to differentiate between
all prefixes a n and a m . But since there are only a finite number of internal states
with which to do this, there are some n and m for which the distinction cannot be
made.
In order to use this type of argument in a variety of situations, it is
convenient to codify it as a general theorem. There are several ways to do this;
the one we give here is perhaps the most famous one.
A Pumping Lemma
The following result, known as the pumping lemma for regular languages, uses
the pigeonhole principle in another form. The proof is based on the observation
that in a transition graph with n vertices, any walk of length n or longer must
repeat some vertex, that is, contain a cycle.
Theorem 4.8
Let L be an infinite regular language. Then there exists some positive integer m
such that any w ∈ L |w| ≥ m can be decomposed as