The Pumping Lemma

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