Motivation
A finite automaton may read an input of arbitrary length, but it has only finitely many states. On a sufficiently long input it must revisit a state. The intervening piece of input can then be repeated or deleted without changing where the rest of the computation begins. This simple loop observation becomes a powerful way to prove that some languages cannot be recognized by any finite automaton.
The proof technique is a game of choices. The alleged automaton determines a pumping length; we then choose a long word; an opponent chooses a legal decomposition of that word; finally we must find a repetition count that takes the word outside the language. A single convenient decomposition is not enough, because an unknown automaton may provide a different loop. We will also see a nonregular language that passes the pumping test, so the test has a definite limit.
Definitions and theorem
Definition 1.4.1
(Powers and length of a word)
Fix a finite alphabet . For a word , write , , and for concatenated copies when is a nonnegative integer. The length of a word is denoted .
Theorem 1.4.2
(Pumping lemma for regular languages)
If is regular, there is an integer such that every with has a decomposition satisfying , , and for every integer .
The order of the quantifiers matters. One must work for every sufficiently long word of . For each such word a suitable decomposition may depend on the word, and then every repetition count must preserve membership. The lemma does not say every decomposition works. It also allows deletion, because is included.
Theorem 1.4.3
(Contrapositive used in nonregularity proofs)
If, for every integer , there exists with such that every decomposition with and has some for which , then is not regular.
The repetition count in the contrapositive may depend on the decomposition. In a particularly clean argument, one count such as works for all legal decompositions. If an adversary offers an illegal decomposition, such as one with , it need not be considered.
Proof: a repeated state produces a loop
Proof
(A repeated state gives a loop)
Suppose is recognized by a complete deterministic finite automaton with states. Set . Let have length at least . Consider the states visited after reading the prefixes of lengths . Two are the same by the pigeonhole principle. Choose indices at which that repetition occurs. Let be the first symbols, the next symbols, and the remaining suffix.
Then and . Reading returns the automaton to the same state reached after . For any , reading exactly times still leaves the automaton at that state; reading then follows the same path to acceptance as in the original word. Hence for all .
This proof supplies a pumping length for every regular language, not necessarily the smallest possible one. It also works when contains no word of length at least : the universal statement about such words is then vacuously true. A nondeterministic automaton poses no problem because every regular language also has an equivalent finite deterministic automaton.
Proof X-ray
Why the pigeonhole count gives a legal loop
The proof has one non-obvious move: it counts prefixes rather than states. The prefixes of lengths visit states, one more than the states available, so two coincide; this is exactly why the loop lies within the first symbols, giving . The strict inequality makes nonempty, so the loop really consumes input. Determinism is used to repeat it: from the repeated state, reading always follows the same path back to that state, so the loop may be run any number of times and then follows the original path to acceptance. Finally, is the number of states of one fixed automaton for , so it does not depend on ; that is the quantifier order of the lemma. Without a finite state set the pigeonhole step has nothing to count.
Worked examples
Worked example 1.4.4
(Equal numbers in two blocks)
Let . Suppose it is regular and let be its pumping length. Choose . Every legal decomposition has , so its nonempty consists only of symbols: for some . Pumping down gives , whose two block lengths differ. It is not in , contradicting the lemma. Thus is not regular.
The word depends on , but it is chosen before the decomposition. The argument treats every legal at once; it does not assume the loop has length one.
Worked example 1.4.5
(A unary language of squares)
Let . Given any proposed pumping length , choose . A legal has length with . Pump once more, taking . The new length is strictly greater than and strictly less than . It is therefore not a square. This proves that is nonregular even over a one-symbol alphabet.
The gap between consecutive squares is the useful feature. Simply saying that a repeated block changes a square length would be insufficient, because some changes could produce a different square.
Worked example 1.4.6
(Palindromes require matching distant symbols)
Let be all palindromes over . For pumping length , choose . The word is a palindrome and is long enough. Every legal nonempty lies among the first letters and is for some . Pumping it down gives , which is not a palindrome because its numbers of symbols on the two sides of the unique differ. Hence is nonregular.
Worked example 1.4.7
(A regular language has some bad decompositions)
Take and the word . With , the decomposition , , is legal with respect to the length bounds, but is not in . This does not contradict regularity: a good decomposition is , , , for which remains in for every . The lemma promises a suitable decomposition, not that all possible loops in the raw word work.
Choosing a useful word
The first attempt at a witness may give the opponent too much freedom. For instance, using to study equal counts introduces several blocks whose changes must be tracked. The shorter word places the entire permitted prefix in the first block. The proof then knows the form of without knowing exactly where it starts or how long it is. In contrast, picking a fixed word such as cannot defeat an arbitrarily large pumping length: it may be shorter than , so the lemma would say nothing about it.
Sometimes the useful repetition count is deletion; sometimes growth is clearer. In the squares argument, deleting up to symbols from also happens to avoid the preceding square for , but the case requires separate attention. Pumping upward uses the simple inequality uniformly. It is good practice to write the exact new length, identify the two adjacent allowed lengths, and show strict inequalities. If the pumped word has the correct length but violates an ordering condition, give that ordering argument instead.
The length condition is a source of information, not a promise that begins at the start of the word. The prefix can have any length from zero up to . For a unary prefix, this uncertainty does not matter: every nonempty contiguous substring is made of the same letter. For a more complicated prefix, a proof must cover loops crossing internal boundaries as well as loops lying within one block.
Other tools can sometimes make the same conclusion easier. For example, a family of prefixes that require pairwise different future responses can establish infinitely many distinguishable states. That approach proves nonregularity through a state lower bound rather than selecting repetitions. The pumping lemma remains useful because a short, correctly quantified word argument often reveals the specific memory requirement students need to understand.
A nonregular language that passes the test
Counterexample mode
Passing the pumping test does not imply regularity
A tempting converse says that a language is regular as soon as every long word of it can be pumped. The pumping lemma is a necessary condition for regularity, not a sufficient one. Consider the language over
It satisfies the pumping conclusion with . For any nonempty word in , choose and let be its first symbol. If the word begins with , pumping changes only the number of leading symbols. With at least one remaining, the original equality remains true; if no remains, the alternative makes the result a member regardless. If the word begins with or , it already has , and repeating or deleting that first symbol preserves both the block form and the alternative . Thus all repetition counts work for the chosen decomposition.
Nevertheless is nonregular. If it were regular, its intersection with the regular language would be regular by the product construction for finite automata. But that intersection is exactly . For a pumping length of this intersection, choose . A legal nonempty is contained in the first symbols, all of which lie before the block. If contains the initial , pumping down removes the only ; otherwise it removes one or more symbols while leaving copies of . In either case the result is outside the intersection. The pumping lemma therefore proves the intersection nonregular, a contradiction.
This construction demonstrates a useful proof strategy: intersect with a simple regular language to expose a difficult part of a language. It also shows exactly why merely finding a pumpable piece in each long word does not construct a finite automaton.
Common mistakes and repair
Common mistake
(Choosing the decomposition yourself)
A nonregularity proof cannot choose the decomposition itself and show that one pumping attempt fails: the automaton's loop might correspond to another decomposition. Choose a word whose first positions constrain all possibilities, then state what every legal must look like.
Common mistake
(Choosing after the word)
Do not exchange the roles of the pumping length and the word. We do not select after seeing a favorable word. Under the assumption of regularity, we accept an arbitrary valid and build a word depending on it. Nor must we identify the actual automaton or its state count; the contradiction works for every positive .
Common mistake
(Pumping out of the language without checking its definition)
Pumping out of a language must be justified from its definition. For the square-length example, the gap calculation shows that no other square is reached. For block languages, one must check both the block order and the required relation among counts. Changing the word is not itself enough to prove nonmembership.
A grammar can repeat two pieces in step, which a finite state set cannot do.
A path to generalization
What changes for context-free languages?
A grammar can repeat two pieces in step, which a finite state set cannot do.
For context-free languages the repetition involves two pieces. There is a such that every with splits as with , and for all . This does not contradict , which is context-free. It does refute : in the window cannot reach both an and a , so pumping leaves one letter count unchanged while another changes.
Summary
Finite-state repetition yields a loop within the first symbols of every sufficiently long accepted word. To prove nonregularity, force every possible loop into a region whose alteration breaks membership. Keep the quantifiers in their original order and use a concrete count such as zero or two. The converse fails: passing the pumping property alone does not guarantee regularity.
Exercises
Quick check
(Prove that is nonregular.)
Choose a word whose first symbols are all .
Solution · Answer
Suppose a pumping length exists and choose . Every legal is with . Pumping down yields . Membership would require , impossible for . This contradicts the lemma.
Quick check
(Prove that is nonregular, using the gap between consecutive powers of two.)
Pump once upward and compare the new length with and .
Solution · Answer
For any proposed , choose . It is long enough since . Every legal loop has length with . Pumping with produces length . Because , this lies strictly between and , hence is not a power of two. The contradiction proves nonregularity.
Quick check
(For , give a pumping length and a valid decomposition for every sufficiently long word. Treat words beginning with either letter.)
A pumping length of suffices; take to be the first symbol.
Solution · Answer
Take . For a nonempty word beginning with , choose and ; repeating or deleting that first leaves an block followed by a block. For a nonempty word beginning with , the word contains no , and choosing the first as leaves a word in . Every required pumping count preserves membership.
Quick check
(For the language above, explain why the word still belongs to after deleting both leading symbols, even though its original membership also used .)
Recall that the definition of is a disjunction.
Solution · Answer
Deleting both symbols gives , whose leading count is zero. The definition of uses an inclusive “or,” so the alternative is enough. In this particular word the equality also remains true, but the zero-leading- alternative would allow unequal numbers as well.