The Pumping Lemma
Here's what the pumping lemma says:
The pumping lemma for regular languages is another way of
proving that a given (infinite) language is not regular.
(The pumping lemma cannot be used to prove that a given
language is regular.)
- If an infinite language is regular, it can be defined by a dfa.
- The dfa has some finite number of states (say, n).
- Since the language is infinite, some strings of the language
must have length > n.
- For a string of length > n accepted by the dfa,
the walk through the dfa must contain a cycle.
- Repeating the cycle an arbitrary number of times must yield
another string accepted by the dfa.
The proof is always by contradiction.
A brief outline of the technique is as follows:
Why this is hard:
- Assume the language L is regular.
- By the pigeonhole principle, any sufficiently long string
in L must repeat some state in the dfa; thus, the walk
contains a cycle.
- Show that repeating the cycle some number of times
("pumping" the cycle) yields a string that is not in L.
- Conclude that L is not regular.
Why we can sometimes pull it off:
- We don't know the dfa (if we did, the language would be regular!).
Thus, we have do the proof for an arbitrary dfa that accepts L.
- Since we don't know the dfa, we certainly don't know the cycle.
- We get to choose the string (but it must be in L).
- We get to choose the the number of times to "pump."
Copyright © 1996 by David Matuszek
Last modified Feb 18, 1996