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, 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

File:Pumping lemma for context-free languages.svg

Proof idea: If $s$ is sufficiently long, its derivation tree w.r.t. a Chomsky normal form grammar must contain some nonterminal $N$ twice on some tree path (upper picture). Repeating $n$ times the derivation part $N$ ⇒...⇒ $vNx$ obtains a derivation for $u{v}^{n}w{x}^{n}y$ (lower left and right picture for $n=0$ and $2$, respectively).

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

$s=uvwxy$

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

1. $|vx|\ge 1$,

2. $|vwx|\le p$, and

3. $u{v}^{n}w{x}^{n}y\in L$ for all $n\ge 0$.

Below is a formal expression of the Pumping Lemma.

$\begin{array}{l}(\mathrm{\forall }L\subseteq {\mathrm{\Sigma }}^{*})\\ (\text{context free}(L)\Rightarrow \\ ((\mathrm{\exists }p\ge 1)((\mathrm{\forall }s\in L)((|s|\ge p)\Rightarrow \\ ((\mathrm{\exists }u,v,w,x,y\in {\mathrm{\Sigma }}^{*})(s=uvwxy\wedge |vx|\ge 1\wedge |vwx|\le p\wedge (\mathrm{\forall }n\ge 0)(u{v}^{n}w{x}^{n}y\in L)))))))\end{array}$

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 is a property of 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=uvwxy$, where $vx$ is non-empty and the length of $vwx$ 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 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 is not violated.

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 \mathbb{\mathbb{N}}$ 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=uvwxy$, where Template:Mvar, and Template:Mvar are substrings, such that $|vx|\ge 1$, $|vwx|\le p$, and $u{v}^{i}w{x}^{i}y\in L$ for every integer $i\ge 0$. By the choice of Template:Mvar and the fact that $|vwx|\le 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:

1. $vwx=a^j$ for some $j\le p$.
2. $vwx=a^j{b}^k$ for some Template:Mvar and Template:Mvar with $j+k\le p$
3. $vwx=b^j$ for some $j\le p$.
4. $vwx=b^j{c}^k$ for some Template:Mvar and Template:Mvar with $j+k\le p$.
5. $vwx=c^j$ for some $j\le p$.

For each case, it is easily verified that $u{v}^{i}w{x}^{i}y$ does not contain equal numbers of each letter for any $i\ne 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.

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

$L=\{b^j{c}^k{d}^l|j,k,l\in \mathbb{\mathbb{N}}\}\cup \{a^i{b}^j{c}^j{d}^j|i,j\in \mathbb{\mathbb{N}},i\ge 1\}$

for Template:Math with e.g. j≥1 choose Template:Mvar to consist only of bTemplate:'s, for Template:Math choose Template:Mvar to consist only of aTemplate:'s; in both cases all pumped strings are still in L.

References

• — Reprinted in:
• Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.