Pumping Lemma

languages

Definition

Pumping Lemma for Regular Languages

(Infinite) regular language have a special property: Every word from a certain length onward can be pumped, i.e. every such word contains a substring that can be repeated arbitrarily often, with the resulting words still belong to the same language.

Let $L$ be an infinite regular language. Then there exists a bound $m>0$ (depending only on $L$) such that for every word $w\in L$ with $|w|\ge m$ there exist words $x,y,z$, such that:

$$w=xyz\text{with }|xy|\le m\text{ and }|y|>0$$

and

$$w_i=x{y}^{i}z\in L\forall i\ge 0$$

A bit more formally:

$$\begin{array}{rl}\exists & m\in \mathbb{N}:\\ \forall & w\in L\text{ with }|w|\ge m:\\ \exists & \text{ Partition }w=xyz\text{ with }|xy|\le m\wedge |y|>0:\\ \forall & i\ge 0:w_i=x{y}^{i}z\in L\end{array}$$

Example

Positive Example

This is the minimal automaton with 3 states for the language $L$, thus $m=3$. Let’s pick an arbitrary word, like:

$$\begin{array}{rl}w& =aab\\ & =xyz\end{array}$$

Thus $x=a$, $y=a$, $z=b$. Clearly:

$$\forall i\ge 0:w=a{a}^{i}b\in L$$

Negative Example

We want to show that if the pumping lemma does not apply to a language $L$, then $L$ is non-regular language.

Given a language $L$:

$$L=\{a^n{b}^n\mid n\ge 1\}$$

Assume that $L$ is regular, i.e. the pumping lemma holds.

Let $w=a^m{b}^m$ with $|w|=2m$. Partition $w$ into

$$w=a^m{b}^m=xyz\text{with }|xy|\le m\wedge |y|>0$$

Because $|xy|\le m$ and the first $m$ symbols of $w$ are all $a$‘s, both $x$ and $y$ consist only of $a$‘s. So we can write:

$$x=a^p,y=a^k,\text{with }k=|y|>0$$

and then:

$$z=a^{m-p-k}{b}^m$$

so that:

$$w=xyz=a^p{a}^k{a}^{m-p-k}{b}^m=a^m{b}^m$$

Consider $i=0$. The pumping lemma claims that $x{y}^{0}z=xz$ must still be in $L$:;

$$xz=a^p{a}^{m-p-k}{b}^m=a^{m-k}{b}^m$$

Here, the number of $a$‘s is $m-k$ and the number of $b$‘s is $m$. Since $k>0$, we have $m-k\ne m$, so:

$$xz=a^{m-k}{b}^m\notin L=\{a^n{b}^n\mid n\ge 1\}$$

because words in $L$ must have the same number of $a$‘s and $b$‘s.

This is a contradiction, which means that the assumption of $L$ being regular must be wrong.