A pumping lemma is a theorem stating that sufficiently long strings in certain classes of formal languages contain parts that can be repeated or removed while remaining in the language. The two standard versions concern regular languages and context-free languages. Their repetition properties arise from repeated states in finite automata or repeated nonterminals in grammatical derivations. Pumping lemmas are chiefly used to prove that a language does not belong to one of these classes: if a language fails the required property, it cannot belong to the class.
Notation and meaning
A formal language is a set of finite strings over an alphabet . The set of all such strings is written . For a string , its length is , and juxtaposition denotes concatenation.
For a string , the expression means consecutive copies of , where is a nonnegative integer. In particular,
where is the empty string. Thus, “pumping” includes both repeating a segment and deleting it.
A pumping length is a positive integer beyond which the lemma guarantees a suitable decomposition of every string in the language. The value depends on the language or on a particular representation of it. It need not be the smallest possible value, and every larger integer is also a valid pumping length.
The lemmas concern strings already in the language. They do not claim that every sufficiently long string over the alphabet belongs to it.
Pumping lemma for regular languages
If is regular, there is an integer such that every with can be written
with
and
The conditions have distinct roles:
- locates the repeated segment within the first symbols.
- makes the repetition nontrivial.
- The universal condition on requires the same decomposition to work for every number of repetitions.
Only the existence of one suitable decomposition is guaranteed. Other decompositions of the same string may fail to preserve membership.
Why the lemma holds
A regular language is recognized by a deterministic finite automaton. Suppose an automaton recognizing has states, and take .
While reading the first symbols of a string, the automaton visits states when the initial state is included. By the pigeonhole principle, two of these visits must be to the same state.
Split the input into:
- : the prefix before the first of these two visits;
- : the nonempty segment read between the visits;
- : the remainder.
Reading returns the automaton to the same state. It can therefore traverse that loop zero times, once, or any number of times, then read and reach the same accepting state. The loop occurs within the first symbols, giving the required length bound.
This argument explains the underlying restriction: an automaton with finitely many states must repeat a state on a sufficiently long computation.
Proving that a language is not regular
The standard proof uses proof by contradiction:
- Assume that the language is regular.
- Let be the pumping length guaranteed by the lemma.
- Choose a string , depending on , with .
- Consider every decomposition satisfying the length conditions.
- Show that, for each such decomposition, some gives .
The fourth step is essential. Demonstrating that one particular decomposition fails does not contradict the lemma, because a different decomposition might work.
Example: equal numbers of two symbols
Consider
Assume is regular and let be its pumping length. Choose
For any permitted decomposition , the condition places entirely within the initial block of 's. Therefore,
for some .
Taking gives
which has unequal numbers of 's and 's and is not in . This contradicts the pumping lemma, so is not regular.
The conclusion is specifically nonregularity. The language is nevertheless context-free.
Pumping lemma for context-free languages
If is context-free, there is an integer such that every with can be written
with
and
Here two segments, and , are pumped together using the same exponent. Either may be empty, but they cannot both be empty. The middle segment is unchanged.
The bounded window may occur anywhere in the string. Unlike the regular-language lemma, this lemma does not restrict the pumpable material to a prefix.
Letters used for the five segments vary between presentations. The mathematical content is determined by which segments are repeated and by the length constraints.
Why the lemma holds
A context-free language is generated by a context-free grammar. Its derivations can be represented by parse trees, whose internal nodes are nonterminal symbols and whose leaves yield the generated string.
The standard proof converts the grammar to Chomsky normal form, treating the empty string separately. In this form, productions have the shapes
A sufficiently long string requires a sufficiently deep parse tree. Because the grammar has finitely many nonterminals, some nonterminal repeats along a root-to-leaf path. The relevant portions of the derivation have the form
Repeating the middle derivation, or omitting it, produces
Choosing repeated occurrences near the bottom of a sufficiently long path bounds the yield . The branching structure ensures that at least one of and is nonempty.
The two pumped segments represent material generated on opposite sides of a recursively expanded nonterminal.
Proving that a language is not context-free
The proof strategy has the same quantifier structure as for regular languages, but it must account for two pumped segments.
Example: three equal blocks
Consider
Assume is context-free, let be its pumping length, and choose
For any permitted decomposition , the window has length at most . It cannot contain both an and a , because doing so would require spanning the entire block of intervening 's as well.
Consequently, the pumped segments and together contain symbols from at most two of the three blocks. At least one symbol type is untouched.
Taking removes at least one symbol because , while leaving all occurrences of at least one other symbol type unchanged. The resulting string cannot have equal counts of , , and . It is therefore outside , contradicting the lemma.
Thus is not context-free. This excludes recognition by a pushdown automaton, not recognition by more powerful computational models.
Quantifiers and common errors
The regular-language lemma has the logical structure
with the decomposition constraints understood.
A nonregularity proof establishes the opposite pattern:
such that the pumped string is outside .
This order explains several frequent mistakes:
- Selecting a convenient decomposition. The proof must defeat every permitted decomposition.
- Using a string outside the language. The lemma makes no promise about such strings.
- Choosing a fixed string without accommodating . The string must be long enough for an arbitrary pumping length.
- Requiring one exponent to work for all decompositions. The exponent may depend on the decomposition.
- Pumping the two context-free segments independently. Both must use the same exponent.
- Treating successful pumping as a membership proof. The lemmas provide necessary conditions, not characterizations.
The context-free lemma has the corresponding quantifier structure, with five segments instead of three.
Scope and limitations
Neither standard pumping lemma has a valid converse: satisfying its pumping property does not, by itself, establish regularity or context-freeness. To establish membership, a proof normally constructs an appropriate automaton, grammar, or equivalent description, or uses established closure properties.
Finite languages satisfy both lemmas vacuously when is greater than every string length in the language. There are then no strings to which the pumping requirement applies.
The lemmas are structural proof tools, not general-purpose algorithms for classifying arbitrarily specified languages. Their usefulness depends on finding a string whose possible decompositions can all be controlled. Some languages resist a direct pumping argument even when their nonmembership can be established by other methods.
For regular languages, the Myhill–Nerode theorem gives a necessary and sufficient characterization using distinguishable prefixes. For context-free languages, Ogden's lemma strengthens the pumping method by allowing selected positions in a string to be marked, constraining where pumping must occur. Closure properties can also transform a difficult language into one with a simpler nonmembership proof.
These methods help distinguish expressive capabilities relevant to compiler construction: finite-state techniques are suited to many lexical patterns, while context-free grammars describe many recursively nested syntactic structures. Pumping arguments establish limits of those formal models; they do not imply that the same language is impossible to recognize using a more powerful model.