The Pumping Lemma for Regular Languages

src: http://www.seas.upenn.edu/~cit596/notes/dave/pumping2.html
Here's what the pumping lemma says:

* 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 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:

* 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 this is hard:

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

Why we can sometimes pull it off:

* We get to choose the string (but it must be in L).
* We get to choose the the number of times to "pump."