pumping lemma (regular languages)

Lemma 1.

Let $L$ be a regular language (a.k.a. type 3 language). Then there exist an integer $n$ such that, if the length of a word $W$ is greater than $n$, then $W=ABC$ where $A,B,C$ are subwords such that

1. 1.

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

2. 2.

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

3. 3.

For all integers $k>0$, it is the case that $AB^{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 language is not regular. (Remember, just because a language happens to be described in terms of an irregular grammar does not automatically preclude the possibility of describing the same language also by a regular grammar.) The idea is to assume that the language is regular, 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 must exist subwords $A,B,C$ such that $W=ABC$ and $B$ must be of length less than $n$. The only possibilities are the following

1. 1.

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

2. 2.

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

3. 3.

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

4. 4.

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

5. 5.

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

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

1. 1.

$AB^{2}C=0^{n+1+v}1^{n+1}0^{n+1}$

2. 2.

$AB^{2}C=0^{n+1}1^{v}0^{u}1^{n+1}0^{n+1}$

3. 3.

$AB^{2}C=0^{n+1}1^{n+1+u}0^{n+1}$

4. 4.

$AB^{2}C=0^{n+1}1^{n+1}0^{u}1^{v}0^{n+1}$

5. 5.

$AB^{2}C=0^{n+1}1^{n+1}0^{n+1+u}$

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

Title pumping lemma (regular languages) PumpingLemmaregularLanguages 2013-03-22 16:21:17 2013-03-22 16:21:17 rspuzio (6075) rspuzio (6075) 9 rspuzio (6075) Theorem msc 68Q42 pumping lemma PumpingLemma