The Pumping Lemma

A DFA has finitely many states. Feed it a string longer than that and, by the pigeonhole principle, it must visit some state twice. The section of input between those two visits took the machine round a loop.

A machine cannot tell how many times it went round a loop — its state is identical either way. So if the original string is accepted, so is the string with that section removed, or repeated any number of times. If any of those strings is outside the language, no such machine can exist.

The lemma is really just the pigeonhole principle plus the observation that finite memory cannot count without bound.

Alphabet (Σ)

The finite set of symbols the machine may read. For everything on this page, Σ = {a, b}.

String and language

A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.

State

The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.

Transition function (δ)

Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.

Accepting state

Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.

Trap or dead state

A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.

1. 1Assume the language is regular, so a pumping length p exists.
2. 2Choose a string s in the language with |s| ≥ p. You choose it — pick one that makes the next steps easy.
3. 3The lemma splits s = xyz with |xy| ≤ p and |y| ≥ 1. You do not choose the split, so your argument must cover every legal one.
4. 4Find some i for which xyⁱz is not in the language. i = 0 or i = 2 nearly always works.
5. 5That contradicts the lemma, so the language is not regular.

The condition |xy| ≤ p is the one that does the real work. For aⁿbⁿ with s = aᵖbᵖ, it forces y to consist only of as — so pumping changes the number of as while leaving the bs alone, and the counts no longer match.

The lemma is a necessary condition for regularity, not a sufficient one. Some non-regular languages satisfy it perfectly well, so a language that pumps successfully has not been proved regular — nothing has been proved at all.

• To prove not regular: the pumping lemma, or the Myhill-Nerode theorem.
• To prove regular: build a DFA, NFA or regular expression. Only a construction settles it.
• The other classic error: choosing the split yourself. The adversary chooses; you must beat every option.