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+1uv}{1}^{n+1}{0}^{n+1}$

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

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

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

5.
$A={0}^{n+1}{1}^{n+1}{0}^{u},B={0}^{v},C={0}^{n+1uv}$
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  20130322 16:21:17 
Last modified on  20130322 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 