Motivation
A finite automaton reading a long word must eventually repeat a state. A context-free grammar has a different kind of finite memory: its nonterminals may repeat along a sufficiently long branch of a parse tree. Repeating a nonterminal creates two nested pieces of derivation that can be inserted together. The context-free pumping lemma makes this observation precise.
The lemma is a necessary condition for a language to be context-free, so its contrapositive can prove that a language is not context-free. It is not a definition or a sufficient test. In a non-context-freeness proof we must defeat every decomposition allowed by the lemma, even though we may choose the word and the pumping exponent.
Definitions
Definition 2.7.1
(Decomposition and pumping)
Let be a language over a finite alphabet. A decomposition of a word is a list of five consecutive strings with . Strings may be empty unless the stated conditions rule them out. Pumping replaces and by the same number of copies, leaving the middle in place. For example, pumping with exponent zero removes both and , while exponent one returns the original word.
Definition 2.7.2
(Chomsky normal form with a protected start rule)
We use a context-free grammar in Chomsky normal form, with rules or , and possibly a protected start rule . For a nonempty generated word, its parse tree has binary variable nodes and terminal leaves. The normal-form conversion is a standard preceding result; the argument below also explains why the empty-word exception causes no problem.
Theorem 2.7.3
(Context-free pumping lemma)
If is context-free, there is an integer such that every with has a decomposition satisfying , , and for every integer .
Theorem 2.7.4
(A non-context-free language)
The language is not context-free.
Proof: a repeated variable on a parse-tree path
Proof
(Pumping from a repeated variable on a longest path)
Take a normal-form grammar for with variables and let . A binary tree whose paths have at most binary variable nodes has at most leaves. Therefore a parse tree for a word of length at least has a root-to-terminal path containing more than variable occurrences. Choose a longest such path. Among its lowest variable occurrences, two have the same variable label; call the higher occurrence and the lower one as well.
Write the terminal yield of the higher subtree as , where is the terminal yield of the lower subtree. The surrounding tree yields before this subtree and after it. Thus the grammar has derivations of the form
The displayed strings are terminal yields of the relevant sibling subtrees, not necessarily symbols produced in a single grammar step. Replacing the lower subtree by a copy of the higher subtree repeats the outer derivation; replacing the higher subtree directly by the lower one removes it. Consequently is generated for every .
The upper occurrence lies within the lowest variable occurrences on a longest path. All paths below it are no longer than the corresponding suffix of that longest path, so its subtree has at most terminal leaves. Hence . The path from upper to lower contains a binary rule, because the occurrences are distinct. Its sibling subtree produces at least one terminal: on this nonempty-word parse tree no variable below the protected start uses an empty rule. Therefore . This is also why pumping actually changes the word length when changes. The possible rule handles only the empty word, which is shorter than and is not used in this tree.
Proof X-ray
Why a longest path matters
A repeated variable somewhere deep in a tree gives a pumpable decomposition, but does not by itself bound the size of its entire subtree. Selecting the repeated occurrences near the bottom of a longest root-to-leaf path controls every branch below the upper occurrence and gives .
Proof that three equal blocks are not context-free
Proof
(Three equal blocks defeat every decomposition)
Assume for contradiction that is context-free, and let be its pumping length. Choose . It belongs to and has length at least . The lemma promises some decomposition satisfying its conditions. We do not choose that decomposition; consider any one that satisfies them.
The contiguous substring has length at most . It cannot contain both an and a , because every such substring also contains all intervening symbols and has length at least . Thus and together contain symbols from at most two of the three block types. At least one type is untouched. Since , at least one of the other counts decreases when we choose .
Deleting and preserves the order of the remaining letters. The untouched type still occurs times, but a touched type occurs fewer than times. The three counts are no longer equal, so . This contradicts the lemma for the promised decomposition. Because the argument covers every allowable decomposition, the contradiction is valid.
Worked examples
Worked example 2.7.5
(A permitted decomposition for a context-free language)
The grammar generates . For , choose , , , and . Pumping gives , which remains in the language. This illustrates the two synchronized pieces; it does not prove the pumping lemma for every word in the language.
Worked example 2.7.6
(A short middle part may cross a boundary)
For , a proposed substring might lie entirely in one block or cross the boundary or the boundary. It cannot reach from an to a with length at most four. Rather than enumerate the exact positions of and , the count argument observes that one entire symbol type is untouched and deletion changes at least one other count.
Worked example 2.7.7
(Simultaneous pumping matters)
For , take , , , and . With the result is . Pumping only would give , but the lemma does not assert that this one-sided operation stays in the language. The same exponent is used for both pieces.
The order of choices
The pumping lemma states a sequence of choices and obligations. First a context-free language supplies one that works for all sufficiently long words. Then any eligible word must have at least one good decomposition. Finally every nonnegative exponent must work for that decomposition.
For a contradiction proof, imagine an adversary announcing . Choose a word depending on . The adversary may select any decomposition obeying the length and nonempty conditions. You must then exhibit an exponent, possibly depending on that decomposition, for which the pumped word leaves the language. The choice of above works uniformly, but not every proof has such a convenient uniform exponent.
A bad decomposition alone proves nothing: a context-free language may also have many decompositions that fail to pump. Nor is it enough to check just the visually obvious split between blocks. The argument must account for pieces that sit inside a block, cross a boundary, or have one of empty.
Counterexample mode
A bad decomposition is not a contradiction
Claim: to refute context-freeness it is enough to find one decomposition of one long word that fails to pump. In , which is context-free, take and the decomposition , , , , , so that and . Pumping down gives , which is not in the language, so this decomposition fails. Yet the language is context-free, and the earlier worked example exhibits a decomposition (, ) that pumps for every exponent. The lemma requires the existence of a good decomposition, so a refutation must defeat every permitted one.
Common mistake
(The word must depend on the pumping length)
In a contradiction proof the pumping length is supplied by the assumed grammar and is unknown. A fixed word such as does not work: if the lemma says nothing about a word of length . Choose the word in terms of , for example .
Common mistake
(Reading the lemma backwards)
The lemma has the form: context-free implies pumpable. Its contrapositive, not pumpable implies not context-free, is what proofs use. The converse, pumpable implies context-free, is not asserted, so showing that some decomposition pumps never proves that a language is context-free.
What the lemma does and does not show
For , the obstruction is that two short pumpable pieces cannot alter all three separated blocks, while equality requires their counts to move together. The fixed intervening block forces the short substring to miss at least one symbol type. The argument uses both the local bound on and the nonemptiness of .
The lemma does not say that every non-context-free language can be disproved by this particular method. Even if a language satisfies the pumping property, that fact alone does not supply a context-free grammar. Closure properties, stronger pumping statements, or other methods may be needed. Conversely, failure to find a good decomposition is not a proof until all permitted decompositions have been excluded.
When applying the lemma to a new language, first check that the selected word belongs to the language for every announced . Then identify what a short contiguous interval cannot cover. Finally calculate a specific pumped result and explain exactly which membership requirement fails. If pumping changes the order as well as the counts, either failure is sufficient, but it should be stated rather than assumed.
A second obstruction: crossed equalities
Consider . Here there are two equalities rather than a requirement that four counts all agree. We can still use the local span of the two pumped pieces. Assume is context-free, take its pumping length , and choose . A substring of length at most cannot contain both an and a : the entire intervening block of symbols lies between them. Similarly, it cannot contain both a and a .
For any allowed decomposition, at least one of the four types appears in . If the changed type is or , its matching partner in the equality is absent from the whole span . If it is or , its partner in is absent. Pumping down decreases the count of a changed type and leaves its partner at . Thus at least one required equality fails, regardless of the other symbols that were deleted. This proves that is not context-free.
The order of the equalities matters. In contrast, is context-free: one grammar generates an equal pair, another generates an equal pair, and a new start symbol concatenates their outputs. A concrete grammar is , , . Stating the grammar and tracing its two independent choices avoids relying on a picture of what a stack can or cannot remember.
The language proof does not need the grammar's actual number of variables or an explicit value of . It works for every positive integer the lemma might supply. This is useful because an assumed grammar in a contradiction may be completely unknown. Choosing one fixed word without reference to would not generally be enough: the unknown pumping threshold could be larger than that word.
Summary
A repeated variable along a long parse-tree path supplies two synchronized pumpable pieces. The subtree-size bound makes their combined span local. In a non-context-freeness proof the word is chosen after the pumping length, but the argument must defeat every permitted decomposition.
Exercises
Quick check
(For and , give a decomposition with nonempty and that pumps within , and calculate its and results.)
Solution · Answer
Take , , , . Pumping down gives and pumping twice gives . Every exponent produces .
Quick check
(Prove that a substring of containing both an and a has length at least .)
Solution · Answer
The substring begins at or before the final and ends at or after the first . It contains those two endpoint symbols and all intervening symbols, for at least positions.
Quick check
(In the proof, suppose is empty but contains one or more symbols and no other symbols. Explain the contradiction after pumping down.)
Solution · Answer
Pumping down deletes at least one and no or . The resulting counts are , less than , and , so the result is outside even though one pumped piece is empty.
Quick check
(A student picks a single decomposition of , shows that it fails when , and concludes non-context-freeness. Identify the missing quantifier and repair the outline.)
Solution · Answer
The lemma allows the grammar to provide any suitable decomposition, not necessarily the student's chosen one. Fix an arbitrary decomposition with and . Its span misses at least one of the three symbol types; deleting the nonempty pair changes another count while leaving the missed count at . Thus every allowed decomposition fails at exponent zero.