[Overview] [Previous] [Next]

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