pumping lemma (context-free languages)


Let L be a context-free language (a.k.a. type 2 languagePlanetmathPlanetmath). Then there exist two integers m and n such that, if the length of a word W is greater than m, then W=ABCDE where A,B,C,D,E are subwords such that

  1. 1.

    The length of the subword BCD is less than n.

  2. 2.

    BD is not be empty.

  3. 3.

    For all integers k>0, it is the case that ABkCDkE belongs to L, where exponentiation denotes repetition of a subword k times.

An important use of this lemma is that it allows one to show that a language is not context-free. (Remember, just because a language happens to be described in terms of a context-sensitive grammar does not automatically preclude the possibility of describing the same language also by a context-free language.) The idea is to assume that the language is context-free, then arrive at a contradictionMathworldPlanetmathPlanetmath via this lemma.

As an illustrative example, consider the following language, which consists of but one terminal symbol, ‘x’ and which consists of all strings of ‘x’ ’s whose length is a perfect squareMathworldPlanetmath. Were this a context-free language, there would exist integers m and n as above. Choose an integer h such that h2>m. Then the word xh2 belongs to our language and the lemma tells us that it can be written as ABCDE so as to satisfy the conditions enumerated above. Write A=xa, B=xb, C=xc, D=xd, E=xe for suitable nonnegative integers a,b,c,d,e. Then we have a+b+c+d+e=k2; by condition , b+d>0 and, by condition , a+kb+c+kd+e would have to be a perfect square because ABkCDkE would be a word of the language. This, however, leads to a contradiction: h2+k(b+d) could not possibly be a perfect square for all k unless b+d=0.

As an exercise, the reader may consider constructing a context-sensitive grammar for this language and posting it as an attachment to this entry (at which time this sentenceMathworldPlanetmath will come down).

Title pumping lemmaPlanetmathPlanetmath (context-free languages)
Canonical name PumpingLemmacontextfreeLanguages
Date of creation 2013-03-22 16:21:10
Last modified on 2013-03-22 16:21:10
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 8
Author rspuzio (6075)
Entry type Theorem
Classification msc 68Q42
Synonym pumping lemma
Related topic PumpingLemmaRegularLanguages