## You are here

Homepumping lemma (regular languages)

## Primary tabs

# 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. 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 $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. $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, $AB^{2}C$ would have the following form:

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

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

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

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

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.

## Mathematics Subject Classification

68Q42*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections