Proving that a language is regular is often easy: just exhibit an automaton or a regular expression. Proving that it is not regular requires a general argument that works against every possible automaton. The pumping lemma is the classic tool for this. It is also one of the topics where students go wrong most often, nearly always through a logical slip with quantifiers rather than a mathematical one.
The intuition: a finite automaton must repeat a state
Let M be a DFA with p states. If M reads a string of length at least p, it passes through at least p + 1 states (counting the start state). By the pigeonhole principle, at least one state appears twice. The stretch of input read between the two visits forms a cycle: the automaton leaves a state and comes back to it.
A cycle can be traversed zero times, once or a hundred times, and the automaton still ends in the same state at the end of the string. So if the original string was accepted, all the "pumped" versions are accepted too.
The statement
If L is regular, there is an integer p ≥ 1 (the pumping length) such that every string s ∈ L with |s| ≥ p can be written as s = xyz with:
- |y| ≥ 1 (the cycle is not empty);
- |xy| ≤ p (the cycle appears within the first p symbols);
- xyⁱz ∈ L for every i ≥ 0.
The second condition follows from the fact that the first repeated state necessarily occurs within the first p symbols read. It is the most useful condition in proofs, because it pins down where y lies.
The logical structure
The statement has the form: there exists p, for every s, there exists a decomposition, for every i. To prove that L is not regular we negate everything, and the quantifiers swap:
for every p, there is s ∈ L with |s| ≥ p such that, for every decomposition s = xyz satisfying conditions 1 and 2, there is an i with xyⁱz ∉ L.
It helps to think of it as a two-player game:
- the adversary picks p;
- you pick the string s, which may depend on p;
- the adversary picks the decomposition xyz, respecting |y| ≥ 1 and |xy| ≤ p;
- you pick i and show that xyⁱz leaves the language.
If you have a winning strategy whatever the adversary does, the language is not regular.
Example 1: aⁿbⁿ
Let L = {aⁿbⁿ : n ≥ 0}. Given p, choose s = aᵖbᵖ. Any decomposition with |xy| ≤ p has x and y made only of a's, because the first p symbols are all a's. So y = aᵏ with k ≥ 1. Pumping with i = 2 gives aᵖ⁺ᵏbᵖ, which has more a's than b's and is not in L. The language is not regular.
Notice how the choice of s did all the work: by putting the a's first and exploiting condition 2, we removed every option from the adversary.
Example 2: strings of square length
Let L = {aⁿ : n is a perfect square}. Given p, choose s = a^(p²). The adversary picks y = aᵏ with 1 ≤ k ≤ p. With i = 2 we get a string of length p² + k. But p² < p² + k ≤ p² + p < (p + 1)², so the length falls strictly between two consecutive squares and is not a square. The string leaves L.
Example 3: palindromes
Let L be the set of palindromes over {a, b}. Choose s = aᵖbaᵖ. Again y consists only of a's from the first half. With i = 0 some a's are removed on the left and the string becomes aᵖ⁻ᵏbaᵖ, which is no longer a palindrome.
Typical mistakes
- Picking a specific p. You cannot say "let p = 5": p is chosen by the adversary and must be treated as arbitrary.
- Picking the decomposition. You do not decide where y is: you must handle every allowed decomposition.
- A string that is too short or outside the language. s must belong to L and have length at least p.
- Using the lemma to prove regularity. The lemma is only a necessary condition. Some non-regular languages still satisfy the pumping conditions; for those a stronger tool is needed, such as the Myhill-Nerode theorem.
Alternatives and shortcuts
It often pays to use closure properties. If L were regular and R is regular, then L ∩ R would be regular too. For example, the language of strings with equally many a's and b's, intersected with a*b*, gives exactly aⁿbⁿ; since the latter is not regular, neither is the original language. One line instead of a full proof.
In short
- An automaton with p states, reading at least p symbols, repeats a state and forms a cycle that can be pumped.
- The lemma guarantees a decomposition xyz with |y| ≥ 1, |xy| ≤ p and xyⁱz in the language for every i.
- To prove non-regularity you play against an adversary who chooses p and the decomposition.
- A clever choice of string, exploiting |xy| ≤ p, is almost always the key.
- The lemma is only necessary: some cases need Myhill-Nerode or closure properties.
