Pumping Lemma (Context-free Languages)

languages

Definition

Pumping Lemma (Context-free Languages)

Infinite context-free languages have a special pumping property: every sufficiently long word contains a middle part that can be repeated.

Let $L$ be an infinite context-free 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 $u,v,x,y,z$, such that:

$$w=uvxyz\text{with }|vxy|\le m\text{ and }|vy|\ge 1$$

and

$$w_i=u{v}^{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=uvxyz\text{ with }|vxy|\le m\wedge |vy|>0:\\ \forall & i\ge 0:w_i=u{v}^{i}x{y}^{i}z\in L\end{array}$$

Important

$$L\text{ is context-free}⟹\text{Pumping Lemma applicable on }L$$

Equivalently:

$$\text{Pumping Lemma NOT applicable on }L⟹L\text{ is NOT context-free}$$

Corollary

Corollary to the pumping lemma

Let $L\subseteq \{a{\}}^{\ast }$, so that

$$L=\{a^{f(n)}\mid n\ge 0\}$$

for a strictly monotonically increasing function $f$ on the natural numbers. If for every natural number $k$ there exists a natural number $n(k)$ such that

$$f(n(k+1))-f(n(k))\ge k,$$

then $L$ cannot be context-free.

In particular, the languages

$$\{a^p\mid p\text{ is prime}\}$$

and

$$\{a^{2^n}\mid n\ge 0\}$$

are not context-free.

Examples

$\{a^n{b}^n{c}^n\mid n\ge 0\}$ is not context-free

Assume that

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

is context-free. Let $m$ be the pumping length of the lemma, and choose

$$w=a^m{b}^m{c}^m.$$

Then

$$|w{|}_a=|w{|}_b=|w{|}_c=m.$$

Since $|w|=3m>m$, we can decompose $w$ as

$$w=uvxyz\text{with }|vxy|\le m.$$

Because $|vxy|\le m$, the substring $vxy$ cannot contain both an $a$ and a $c$. Hence it cannot cover all three blocks at once. Therefore, $vxy$ lies entirely inside the $a$-block, the $b$-block, or over at most two adjacent blocks.

In particular, $vxy$ cannot contain both symbols $a$ and $c$ simultaneously, so either

$$|vxy{|}_a=0\text{or}|vxy{|}_c=0.$$

Pumping then changes the number of $a$‘s and $c$‘s unequally, so for some $i$ the word $u{v}^{i}x{y}^{i}z$ is not in $L$.

This contradicts the pumping lemma. Therefore, $L$ is not context-free.