# Pumping Lemma for CFG - Automata Theory

## Lemma

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

## Applications of Pumping Lemma

Generally Pumping lemma is used to check the context of grammar. Let’s check this with an example and show how it is checked.

## Problem

Explore that the language is context free or not.

### Solution

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

For this you need to select a number n of the pumping lemma. Then, take z as 0n1n2n.

Break z into uvwxy, where

|vwx| ≤ n and vx ≠ ε.

So, vwx doesn’t include both 0s and 2s, since the last 0 and the first 2 are at least (n+1) positions apart. Following are the two cases: −

Case 1vwx 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.

Case2− vwx has no 0s.

There will be some contradiction here.

So, its derived that L is not a context-free language.

## Automata Theory Related Practice Tests

Automata Theory Topics