Pumping lemma for context-free languages

In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma,[1] is a lemma that gives a property shared by all context-free languages and generalizes the pumping lemma for regular languages.

The pumping lemma can be used to construct a refutation by contradiction that a specific language is not context-free.

Conversely, the pumping lemma does not suffice to guarantee that a language is context-free; there are other necessary conditions, such as Ogden's lemma, or the Interchange lemma.

is context-free, then there exists some integer

(called a "pumping length")[2] such that every string

, such that Below is a formal expression of the Pumping Lemma.

The pumping lemma for context-free languages (called just "the pumping lemma" for the rest of this article) describes a property that all context-free languages are guaranteed to have.

The property is a property of all strings in the language that are of length at least

is a constant—called the pumping length—that varies between context-free languages.

The pumping lemma states that

produces a string that is still in the language.

It is often useful to repeat zero times, which removes

is what gives the pumping lemma its name.

Finite languages (which are regular and hence context-free) obey the pumping lemma trivially by having

equal to the maximum string length in

As there are no strings of this length the pumping lemma is not violated.

The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be "pumped" without producing strings outside L. For example, if

In particular, neither the prime numbers nor the square numbers are context-free.

can be shown to be non-context-free by using the pumping lemma in a proof by contradiction.

First, assume that L is context free.

By the pumping lemma, there exists an integer p which is the pumping length of language L. Consider the string

in L. The pumping lemma tells us that s can be written in the form

, it is easily seen that the substring vwx can contain no more than two distinct symbols.

That is, we have one of five possibilities for vwx: For each case, it is easily verified that

does not contain equal numbers of each letter for any

This contradicts the definition of L. Therefore, our initial assumption that L is context free must be false.

is not context-free using a precursor of the pumping lemma.

[3] While the pumping lemma is often a useful tool to prove that a given language is not context-free, it does not give a complete characterization of the context-free languages.

If a language does not satisfy the condition given by the pumping lemma, we have established that it is not context-free.

On the other hand, there are languages that are not context-free, but still satisfy the condition given by the pumping lemma, for example for s=bjckdl with e.g. j≥1 choose vwx to consist only of b's, for s=aibjcjdj choose vwx to consist only of a's; in both cases all pumped strings are still in L.[4]