pumping lemma (context-free languages)

Let $L$ be a context-free language (a.k.a. type 2 language). Then there existtwo integers $m$ and $n$ such that, if the length of a word $W$ is greaterthan $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 languageis not context-free. (Remember, just because a language happens to be describedin terms of a context-sensitive grammar does not automatically preclude thepossibility of describing the same language also by acontext-free language.) The idea is to assume that the language iscontext-free, then arrive at a contradiction via this lemma.

As an illustrative example, consider the following language, which consists ofbut one terminal symbol, ‘x’ and which consists of all strings of ‘x’ ’s whoselength is a perfect square. Were this a context-free language, there wouldexist 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 thatit 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$ wouldhave to be a perfect square because $A{B}^{k}C{D}^{k}E$ would be a word of thelanguage. 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 context-sensitivegrammar for this language and posting it as an attachment to this entry(at which time this sentence will come down).