Pumping Lemma (Regular Languages)

languages

Definition

Pumping Lemma (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$$

Short (quantifier) form:

$$\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}$$

Important

$$L\text{ is regular}⟹\text{Pumping Lemma applicable on }L$$

Equivalently:

$$\text{Pumping Lemma NOT applicable on }L⟹L\text{ is NOT regular}$$

Pigeonhole Principle

The proof uses the pigeonhole principle. Let $M$ be a deterministic finite automaton with $m$ states, and let $w\in L$ with $|w|\ge m$.

After reading the first $m$ symbols of $w$, the automaton has visited $m+1$ states, including the initial state. Since there are only $m$ states, at least one state must occur twice.

Intuitively, $m$ is the length beyond which the automaton can no longer keep seeing only new states. From that point onward, some state must repeat, so a loop appears in the computation.

Intuition

The first $m$ input symbols produce $m+1$ visited states. Since there are only $m$ states, one state must repeat.

In the picture above, the repeated state lies inside the first $m$ input symbols. The segment between the two occurrences is $y$, and together with $x$ it stays to the left of the boundary, so $|xy|\le m$.

If the input word is written as $w=xyz$, then the automaton can read $y$ zero or more times without changing the state reached after $xyz$.

Therefore, every word of length at least $m$ can be decomposed as $w=xyz$ with $|xy|\le m$ and $|y|>0$.

Observations

What the pumping lemma gives

• First choose a pumping length $m$ for the language.

• For a deterministic finite automaton with $n$ states, a natural choice is $m=n$.

• The bound $m$ does not have to be minimal.

• Then choose any word $w\in L$ with $|w|\ge m$.

• For that word, find one decomposition $w=xyz$ with $|xy|\le m$ and $|y|>0$.

• Then every pumped word $x{y}^{i}z$ must still lie in $L$.

Common mistake $x{y}^{i}z$ does not describe the whole language. It only describes the pumped versions of one chosen word.

So one example family is enough to show how pumping works, but it is not a full description of $L$.

Every sufficiently long word in a regular language contains a repeatable middle segment $y$, because a finite automaton must revisit a state (see pigeonhole principle).

Examples

Positive Example

This automaton has two states, so $m=2$ would already work. However, the pumping length does not have to be minimal. We may also choose the larger bound $m=3$.

Why $m=3$ and $q_0\stackrel{a}{\to }{q}_0\stackrel{a}{\to }{q}_0\stackrel{b}{\to }{q}_1$ The pumping lemma only says that there exists some bound $m$. It does not require the smallest possible one. So although $m=2$ already works for this automaton, $m=3$ is also a valid pumping length.

After fixing $m=3$, we choose a word with length at least $3$. The word $b$ is too short, and $ab$ is also too short. A simple accepted word with length $3$ is $aab$.

Its run is

$$q_0\stackrel{a}{\to }{q}_0\stackrel{a}{\to }{q}_0\stackrel{b}{\to }{q}_1.$$

We choose this chain because its word length reaches the chosen pumping length and it shows the repeated state $q_0$ explicitly.

Take the word

$$w=aab.$$

We can therefore split the word as

$$w=xyz$$

with

$$x=a,y=a,z=b.$$

Here, $y$ is the loop part: the automaton stays in $q_0$ while reading it. Since $q_0$ also has an $a$-loop, we may repeat $y$ any number of times. Thus:

$$x{y}^{i}z=a{a}^{i}b\in L\forall i\ge 0.$$

Coverage $a{a}^{i}b$ only describes the pumped versions of the chosen word $aab$. It does not describe the whole language $L$, because the word $b$ is also in $L$ but cannot be written in the form $a{a}^{i}b$.

The family

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 (because $|a^m|=m$), both $x$ and $y$ consist only of $a$‘s. So we can write:

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

and then, by removing the prefix $x$ and $y$, we construct a suffix $z$:

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

so that:

$$w=xyz=\underset{\text{prefix}}{\underbrace{a^p{a}^k}}\underset{\text{suffix}}{\underbrace{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.

Negative Example

Assume that the language $L$ is regular:

$$L=\{uu\mid u\in \{0,1{\}}^{\ast }\}$$

The trick is to put the symbol with $m$ as exponent upfront. So we could choose:

$$xyz=0^{m}100^{m}10$$

as word.

Therefore, the word $xy$ only consists of $0$s, given the constraint $|xy|\le m$.

For $i=0$, we get:

$$x{y}^0=xz=0^{m-|y|}100^{m}10$$

Looking at the construction of $L$, we can infer that $xz\notin L$ as we caused a non-symmetric pattern, given $|y|>0$. Note that works for any non-negative integer $i\ne 1$.

This contradicts the assumption above that $L$ is regular. Thus, $L$ is not regular.

$\{xy{y}^r{x}^r\mid x,y\in \{a,b,c{\}}^{\ast }\}$

Let $L=\{xy{y}^r{x}^r\mid x,y\in \{a,b,c{\}}^{\ast }\}$. Assume that $L$ is regular, i.e. the pumping lemma is applicable.

Then, there exists some $m$ such that for all $w\in L$ with $|w|\ge m$ and all $i\ge 0$ that we can denote $w$ as:

$$w=x{y}^{i}z\text{with }0<|xy|\le m\wedge |y|>0$$

Choose $w=a^{m}bb{a}^m\in L$ with $|w|=2m+2>m$.

Why this word works $m$ symbols are all the same, so that any substring $y$ with $|xy|\le m$ must lie completely inside that repeated block.

This is useful because pumping $y$ changes only that part of the word. The remaining suffix stays fixed, so any property that requires the left and right parts to match will be destroyed.

In other words, the word is chosen so that the pumping lemma is forced to act exactly where the language’s defining symmetry is most fragile.

Now, we partition $w$ into three components:

$$w=a^{m}bb{a}^m=x{y}^{i}z\text{with }0<|xy|\le m\wedge |y|>0$$

Given that $|a^m|=m$, it follows that $xy=a^m$. We rewrite $w$ as:

$$w=\underset{=xy}{\underbrace{a^m}}\underset{=z}{\underbrace{bb{a}^m}}=xyz$$

Choose $i=0$. We get:

$$w^{\prime }=x{y}^{0}z=xz=a^{m-|y|}bb{a}^m$$

Looking at the definition of $L$ and $|y|>0$, it follows that $w^{\prime }\notin L$. This is contradicts the initial claim that $L$ is regular, given that every word has to have a partition such that for ALL $i$ the partition is equal to the original word.

Therefore, $L$ is not regular.

Furthermore, given that $L$ is equivalent to the language of palindromes:

$$L_P=\{w{w}^r\mid w\in \{a,b,c{\}}^{\ast }\}$$

$\{xy{x}^r{y}^{\mid }x,y\in \{a,b,c{\}}^{\ast }\}$

Let $L=\{xy{x}^r{y}^{\mid }x,y\in \{a,b,c{\}}^{\ast }\}$. Assume that $L$ is regular, i.e. the pumping lemma is applicable.

Then there exists some $m$ such that all, for any $i\ge 0$, there exists a partition $w=x{y}^{i}z$ with $|xy|\le m$ and $|y|>0$.

Choose $w=a^{m}b{a}^{m}b$. Then, there exists some partition such that:

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

Given that $|a^m|=m$, it follows that $xy=a^m$, given that $|xy|\le m$. Rewrite $w$ as:

$$w=\underset{=xy}{\underbrace{a^m}}\underset{=z}{\underbrace{b{a}^{m}b}}=xyz$$

Choose $i=0$. Then:

$$w^{\prime }=x{y}^{0}z=xz=a^{m-|y|}b{a}^{m}b$$

Given that $y\ne \epsilon$, it follows that $w^{\prime }\notin L$. That contradicts the initial statement that $L$ is regular, i.e. $L$ is non-regular.