Pumping lemma for context-free languages

This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (July 2009)

The pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property that all context-free languages have.

Its primary use is to prove a language is not context-free.

• Because also "L-systems" and "Turing machines" have this property and they "contain" context-free languages.
• Note that it cannot be used to prove that any arbitrary non-context-free language is not context-free. In some cases the more generalized Ogden's lemma must be used.

Formal statement

If a language L is context-free, then there exists some integer p > 0 such that any string s in L with |s| ≥ p (where p is a pumping length) can be written as

s = uvxyz

with substrings u, v, x, y and z, such that |vxy| ≤ p, |vy| ≥ 1, and

uv ⁱxy ⁱz is in L for every integer i ≥ 0.

Informal statement and explanation

The pumping lemma for context-free languages (called just "the pumping lemma" from now on) 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 = uvxyz, where vy is non-empty and the length of vxy is at most p, such that repeating v and y any (and the same) number of times in s produces a string that is still in the language (it's possible and often useful to repeat zero times, which removes v and y from the string). This process of "pumping up" additional copies of v and y is what gives the pumping lemma its name.

Note that 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.

The pumping lemma is often used to prove languages non-context-free by showing that some string s in the language of length at least p does not have the properties outlined above, i.e. that it cannot be "pumped" without producing some strings that are not in the language.

Use of lemma

The pumping lemma for context-free languages can be used to show that certain languages are not context-free.

For example, we can show that language L = {aⁱbⁱcⁱ | i > 0} is not 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^pb^pc^p in L. The pumping lemma tells us that s can be written in the form s = uvxyz, where u,v,x,y, and z are substrings, such that , , and uvⁱxyⁱz is in L for every integer . By our choice of s and the fact that , it is easily seen that the substring vxy can contain no more than two distinct letters. That is, we have one of five possibilities for vxy:

1. vxy = a^j for some .
2. vxy = a^jb^k for some j and k with .
3. vxy = b^j for some .
4. vxy = b^jc^k for some j and k with .
5. vxy = c^j for some .

For each case, it is easily verified (exercise left to the reader) that uvⁱxyⁱz does not contain equal numbers of each letter for any . Thus, uv²xy²z does not have the form aⁱbⁱcⁱ. This contradicts the definition of L. Therefore, our initial assumption that L is context free must be false.

See also

• Pumping lemma for regular languages
• Formal languages

References

• Bar-Hillel, Y.; Perles, M. and Shamir, E. (1961). "On formal properties of simple phrase-structure grammars". Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14: 143–177. 
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.