Pumping lemma for context-free languages

Short description: Type of pumping lemma

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

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 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=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 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 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 $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 L is context free. By the pumping lemma, there exists an integer p which is the pumping length of language L. Consider the string $s=a^p{b}^p{c}^p$ in L. The pumping lemma tells us that s can be written in the form $s=uvwxy$, where u, v, w, x, and y 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 s and the fact that $|vwx|\le p$, 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:

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

In each case, $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 L. Therefore, our initial assumption that L 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, 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 s=b^jc^kd^l with e.g. j≥1 choose vwx to consist only of b's, for s=aⁱb^jc^jd^j choose vwx to consist only of a's; in both cases all pumped strings are still in L. To prove that a given language is context-free, it is sufficient to construct a pushdown automaton that accepts it.

References

• Bar-Hillel, Y.; Perles, Micha; Shamir, Eli (1961). "On formal properties of simple phrase-structure grammars". Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14 (2): 143–172.  — Reprinted in (Bar-Hillel 1964)

• Bar-Hillel, Y. (1964). Language and Information: Selected Essays on their Theory and Application. Addison-Wesley series in logic. Addison-Wesley. pp. 116–150. OCLC 783543642. 

• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. 27. Providence, RI: American Mathematical Society. p. 90. ISBN 978-0-8218-4480-9. http://webpages.math.luc.edu/~lauve/papers/wordsbook.pdf.  — Also see "Aaron Berstel's website". https://www-igm.univ-mlv.fr/~berstel/. 

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. https://archive.org/details/introductiontoau00hopc. 

• Kreowski, Hans-Jörg (1979). "A pumping lemma for context-free graph languages". in Claus, Volker; Ehrig, Hartmut; Rozenberg, Grzegorz. Graph-Grammars and Their Application to Computer Science and Biology. Lecture Notes in Computer Science. 73. Berlin, Heidelberg: Springer. pp. 270–283. doi:10.1007/BFb0025726. ISBN 978-3-540-35091-0. https://link.springer.com/chapter/10.1007%2FBFb0025726. 

• Scheinberg, Stephen (1960). "Note on the Boolean Properties of Context Free Languages". Information and Control 3 (4): 372–375. doi:10.1016/s0019-9958(60)90965-7. https://core.ac.uk/download/pdf/82210847.pdf. 

• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. https://archive.org/details/introductiontoth00sips. "Section 1.4: Nonregular Languages, resp. Section 2.3: Non-context-free Languages"