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, uvⁱxyⁱz ∈ 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ⁿyⁿzⁿ | 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ⁿ1ⁿ2ⁿ.

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.