[Overview] [Previous] [Next]

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.)

The proof is always by contradiction. A brief outline of the technique is as follows:

Why this is hard: Why we can sometimes pull it off:

Copyright © 1996 by David Matuszek
Last modified Feb 18, 1996