Pumping lemma for context-free languages

Template:Short description In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma,Template:Sfn 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.

Formal statement

Template:Dark mode invert If a language $L$ is context-free, then there exists some integer $p \geq 1$ (called a "pumping length")Template:Sfn such that every string $s$ in $L$ that has a length of $p$ or more symbols (i.e. with $| s | \geq p$ ) can be written as

$s = u v w x y$

with substrings $u, v, w, x$ and $y$ , such that

$| v x | \geq 1$ ,
$| v w x | \leq p$ , and
$u v^{n} w x^{n} y \in L$ for all $n \geq 0$ .

Below is a formal expression of the Pumping Lemma.

$\begin{matrix} (\forall L \subseteq Σ^{*}) \\ (context free (L) \Rightarrow \\ ((\exists p \geq 1) ((\forall s \in L) ((| s | \geq p) \Rightarrow \\ ((\exists u, v, w, x, y \in Σ^{*}) (s = u v w x y \land | v x | \geq 1 \land | v w x | \leq p \land (\forall n \geq 0) (u v^{n} w x^{n} y \in L))))))) \end{matrix}$

Informal statement and explanation

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 holds for all strings in the language that are of length at least $p$ , where $p$ is a constant—called the pumping length—that varies between context-free languages.

Say $s$ is a string of length at least $p$ that is in the language.

The pumping lemma states that $s$ can be split into five substrings, $s = u v w x y$ , where $v x$ is non-empty and the length of $v w x$ is at most $p$ , such that repeating $v$ and $x$ the same number of times ( $n$ ) in $s$ produces a string that is still in the language. It is often useful to repeat zero times, which removes $v$ and $x$ from the string (this is "pumping down"). This process of "pumping up" $s$ with additional copies of $v$ and $x$ is what gives the pumping lemma its name.

Finite languages (which are regular and hence context-free) obey the pumping lemma trivially by having $p$ equal to the maximum string length in $L$ plus one. As there are no strings of this length the pumping lemma holds vacuously.

Usage of the lemma

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

For example, if $S \subset ℕ$ is infinite but does not contain an (infinite) arithmetic progression, then $L = {a^{n} : n \in S}$ is not context-free. In particular, neither the prime numbers nor the square numbers are context-free.

For example, the language $L = {a^{n} b^{n} c^{n} | n > 0}$ can be shown to be non-context-free by using the pumping lemma in a proof by contradiction. First, assume that Template:Mvar is context free. By the pumping lemma, there exists an integer Template:Mvar which is the pumping length of language Template:Mvar. Consider the string $s = a^{p} b^{p} c^{p}$ in Template:Mvar. The pumping lemma tells us that Template:Mvar can be written in the form $s = u v w x y$ , where Template:Mvar, and Template:Mvar are substrings, such that $| v x | \geq 1$ , $| v w x | \leq p$ , and $u v^{i} w x^{i} y \in L$ for every integer $i \geq 0$ . By the choice of Template:Mvar and the fact that $| v w x | \leq p$ , it is easily seen that the substring Template:Mvar can contain no more than two distinct symbols. That is, we have one of five possibilities for Template:Mvar:

$v w x = a^{j}$ for some $j \leq p$ .
$v w x = a^{j} b^{k}$ for some Template:Mvar and Template:Mvar with $j + k \leq p$
$v w x = b^{j}$ for some $j \leq p$ .
$v w x = b^{j} c^{k}$ for some Template:Mvar and Template:Mvar with $j + k \leq p$ .
$v w x = c^{j}$ for some $j \leq p$ .

In each case, $u v^{i} w x^{i} y$ does not contain equal numbers of each letter for any $i \neq 1$ . Thus, $u v^{2} w x^{2} y$ does not have the form $a^{i} b^{i} c^{i}$ . This contradicts the definition of Template:Mvar. Therefore, our initial assumption that Template:Mvar is context free must be false.

In 1960, Scheinberg proved that $L = {a^{n} b^{n} a^{n} | n > 0}$ is not context-free using a precursor of the pumping lemma.Template:Sfn

While the pumping lemma is often a useful tool to prove that a given language is not context-free, there are languages that are not context-free, but still satisfy the condition given by the pumping lemma, for example $L = {b^{j} c^{k} d^{l} | j, k, l \in ℕ} \cup {a^{i} b^{j} c^{j} d^{j} | i, j \in ℕ, i \geq 1}$ For $s = b^{j} c^{k} d^{l}$ with e.g. $j \geq 1$ , choose $v w x$ to consist only of $b$ 's, for $a^{i} b^{j} c^{j} d^{j}$ , choose $v w x$ to consist only of $a$ 's. In both cases all pumped strings are still in $L$ .Template:Sfn