pumping lemma (regular languages)

Lemma 1.

Let $L$ be a regular language (a.k.a. type 3 language). Then there existan integer $n$ such that, if the length of a word $W$ is greaterthan $n$, then $W\mathrm{=}A\mathit{}B\mathit{}C$ where $A\mathrm{,}B\mathrm{,}C$ are subwords such that

1. The length of the subword $B$ is less than $n$.

2. The subword $B$ cannot be empty (although one of $A$ or $C$ mighthappen to be empty).

3. For all integers $k>0$, it is the case that $A{B}^{k}C$ belongs to $L$,where exponentiation denotes repetition of a subword $k$ times.

An important use of this lemma is to show that a languageis not regular. (Remember, just because a language happens to be describedin terms of an irregular grammar does not automatically preclude thepossibility of describing the same language also by aregular grammar.) The idea is to assume that the language isregular, then arrive at a contradiction via this lemma.

An example of such a use of this lemma is afforded by the language

$$L=\{0^p{1}^q{0}^p\mid p,q>0\}.$$

Let $n$ be the number whose existence is guaranteed by the lemma.Now, consider the word $W=0^{n+1}{1}^{n+1}{0}^{n+1}$. There mustexist subwords $A,B,C$ such that $W=ABC$ and $B$ must be of length less than $n$. The only possibilities are the following

1. $A=0^u,B=0^v,C=0^{n+1-u-v}{1}^{n+1}{0}^{n+1}$

2. $A=0^{n+1-u},B=0^u{1}^v,C=1^{n+1-v}{0}^{n+1}$

3. $A=0^{n+1}{1}^v,B=1^u,C=1^{n+1-u-v}{0}^{n+1}$

4. $A=0^{n+1}{1}^{n+1-v},B=1^v{0}^u,C=0^{n+1-u}$

5. $A=0^{n+1}{1}^{n+1}{0}^u,B=0^v,C=0^{n+1-u-v}$

In these cases, $A{B}^{2}C$ would have the following form:

1. $A{B}^{2}C=0^{n+1+v}{1}^{n+1}{0}^{n+1}$

2. $A{B}^{2}C=0^{n+1}{1}^v{0}^u{1}^{n+1}{0}^{n+1}$

3. $A{B}^{2}C=0^{n+1}{1}^{n+1+u}{0}^{n+1}$

4. $A{B}^{2}C=0^{n+1}{1}^{n+1}{0}^u{1}^v{0}^{n+1}$

5. $A{B}^{2}C=0^{n+1}{1}^{n+1}{0}^{n+1+u}$

It is easy to see that, in each of these five cases, $A{B}^{2}C\notin L$.Hence $L$ cannot be a regular language.