Pumping Lemma

languages

Definition

Definition for Regular 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}$$

Link to original

Definition for Context-free 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}$$

Link to original