Definition
Pumping Lemma (Context-free Languages)
Infinite context-free languages have a special pumping property: every sufficiently long word contains a middle part that can be repeated.
Let
be an infinite context-free language. Then there exists a bound (depending only on ) such that for every word with there exist words , such that: and
Short (quantifier) form:
Important
Equivalently:
Corollary
Corollary to the pumping lemma
Let
, so that for a strictly monotonically increasing function
on the natural numbers. If for every natural number there exists a natural number such that then
cannot be context-free. In particular, the languages
and
are not context-free.
Examples
is not context-free Assume that
is context-free. Let
be the pumping length of the lemma, and choose Then
Since
, we can decompose as Because
, the substring cannot contain both an and a . Hence it cannot cover all three blocks at once. Therefore, lies entirely inside the -block, the -block, or over at most two adjacent blocks. In particular,
cannot contain both symbols and simultaneously, so either Pumping then changes the number of
‘s and ‘s unequally, so for some the word is not in . This contradicts the pumping lemma. Therefore,
is not context-free.