pumping lemma (contextfree languages)
Let $L$ be a contextfree language (a.k.a. type 2 language^{}). 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.
The length of the subword $BCD$ is less than $n$.

2.
$BD$ is not be empty.

3.
For all integers $k>0$, it is the case that $A{B}^{k}C{D}^{k}E$ 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 contextfree. (Remember, just because a language happens to be described in terms of a contextsensitive grammar does not automatically preclude the possibility of describing the same language also by a contextfree language.) The idea is to assume that the language is contextfree, then arrive at a contradiction^{} 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 square^{}. Were this a contextfree language, there would exist integers $m$ and $n$ as above. Choose an integer $h$ such that ${h}^{2}>m$. Then the word ${x}^{{h}^{2}}$ 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={x}^{a}$, $B={x}^{b}$, $C={x}^{c}$, $D={x}^{d}$, $E={x}^{e}$ for suitable nonnegative integers $a,b,c,d,e$. Then we have $a+b+c+d+e={k}^{2}$; by condition , $b+d>0$ and, by condition , $a+kb+c+kd+e$ would have to be a perfect square because $A{B}^{k}C{D}^{k}E$ would be a word of the language. This, however, leads to a contradiction: ${h}^{2}+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 contextsensitive grammar for this language and posting it as an attachment to this entry (at which time this sentence^{} will come down).
Title  pumping lemma^{} (contextfree languages) 

Canonical name  PumpingLemmacontextfreeLanguages 
Date of creation  20130322 16:21:10 
Last modified on  20130322 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 