# Pumping Lemma for CFG

### Lemma

If **L** is a context-free language, there is a pumping length **p** such that any string **w ∈ L** of length **≥ p** can be written as **w = uvxyz**, where **vy ≠ ε, |vxy| ≤ p**, and for all **i ≥ 0, uvixyiz ∈ L**.

### Applications of Pumping Lemma

Pumping lemma is used to check whether a grammar is context free or not. Let us take an example and show how it is checked.

**Problem**

Find out whether the language **L= {x ^{n}y^{n}z^{n} | n ≥1}** is context free or not.

**Solution −**

Let **L** is context free. Then, **L** must satisfy pumping lemma.

At first, choose a number **n** of the pumping lemma. Then, take **z**as 0^{n}1^{n}2^{n}.

Break **z** into **uvwxy,** where

**|vwx| ≤ n and vx ≠ ε.**

Hence **vwx** cannot involve both 0s and 2s, since the last 0 and the first 2 are at least (n+1) positions apart. There are two cases −

**Case 1** − **vwx** has no 2s. Then **vx** has only 0s and 1s. Then**uwy**, which would have to be in **L**, has **n** 2s, but fewer than **n** 0s or 1s.

**Case 2** − vwx has no 0s.

Here contradiction occurs.

Hence, **L** is not a context-free language.