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\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$ might happen 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 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. $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.

Title	pumping lemma (regular languages)
Canonical name	PumpingLemmaregularLanguages
Date of creation	2013-03-22 16:21:17
Last modified on	2013-03-22 16:21:17
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	9
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 68Q42
Synonym	pumping lemma
Related topic	PumpingLemma