# Pumping Lemma for Context Free Languages

**Pumping Lemma for Context Free Languages**

The **Pumping Lemma **is made up of two words, in which, the word **pumping **is used to generate many input strings by pushing the symbol in input string one after another, and the word **Lemma **is used as intermediate theorem in a proof.

*Pumping lemma** is a method to prove that certain languages are not context free.*

The set of all context free language is identical to the set of languages accepted by Push down Automata.

**Theorem: **

If L be a Context free language, then there is a constant ‘n’ depending only on L such that, if **w ****?**** ****L** and |w| >= n, then w may be divided into five pieces **w = uvxyz, **satisfying the following conditions.

- For all i >= 0, uv
^{i}xy^{i}z ? L. - |vy| >= 1
- |vxy| <= p

**Proof:**

Let G be in Chomsky normal form (CNF). It does not contain any empty string. As we know the right hand side of productions in CNF contain maximum two variables. So, the derivation tree representing G is a binary tree in which, no node contains two children.

### How to Apply Pumping Lemma?

We can apply pumping lemma in context free language to prove that given language is not context free. The steps needed to prove that given languages is not context free are given below:

**Step 1: **Let **L** is a context free language, and we will get contradiction. Let n be a natural number obtained by pumping lemma.

**Step 2: **Now choose a string w ? L where |w| >= n. By using pumping lemma, we can write w = uvxyz with |vy| >= 1 and |vxy| <= n.

**Step 3: **Find suitable i, so that uv^{i}xy^{i}z ? L. It contradicts our assumption and it is proved that given languages is not context free.

**Example 1:**

Let L= { a^{n}b^{n}c^{n} | n>=0 }. By using pumping lemma show that **L is not context free language.**

**Solution:**

**Step 1: **Let L is a context free language, and we will get contradiction. Let n be a natural number obtained by pumping lemma.

**Step 2: **Let w = a^{n}b^{n}c^{n } ** **where| w |>= 3n. By using pumping lemma we can write w = uvxyz with |vy| >= 1 and |vxy| <= n.

**Step 3: **In step 3, we consider two cases.

**Case 1:**Here, v and y contain only one type of alphabet symbol, i.e. both contains only a’s.

Here, uvxyz = a^{n}b^{n}c^{n}

Let i = 2

Then we have uv^{2}xy^{2}z, which pumped more a’s into the string, but the number of b’s remain same. It contradicts our assumption, and it is proved that given language is not context free.

**Case 2:**

In given context free language, we have equal number of a’s, b’s and c’s. The possible substring from given language a^{n}b^{n}c^{n }can be ab and bc, but not ba, ca, ac and cb.

If we choose substring v and y as combination of a and b or b and c.

Then uv^{2}xy^{2}z may contain equal number of three alphabet symbols but not in correct order. The resulting string is of the form

**aaaa.aaaaaaaaa..aabb…bbbcc…..bcccbc**

Here not all b’s follows a’s and not all c’s follows b’s. Hence it cannot be member of context free language L and a contradiction occurs. Both the cases result in contradictions so L is not context free language.

**Example 2:**

Let L= { a^{n}b^{n}a^{n} | n> 0 }. By using pumping lemma show that L is not context free language.

**Solution:**

**Step 1: **Let L is a context free language and we will get contradiction. Let n be a natural number obtained by pumping lemma.

**Step 2: **Let w = a^{n}b^{n}a^{n } ** **where| w |>= n. By using pumping lemma we can write w = uvxyz with |vy| >= 1 and |vxy| <= n.

**Step 3: **In step 3 we consider two cases:

**Case 1: **When both v and y contains equal number of a’s and b’s.

Let, i = 2

Then uv^{2}xy^{2}z = a^{n+k }b^{ n+k }a^{ n } or a^{ n} b^{ n+k } a^{n+k } which is not in L.

**Case 2: **Allwords in a^{n}b^{n}a^{n }have one occurrence of substring ab or ba no matter what n is.

Let, i = 2

Then uv^{2}xy^{2}z will have more than one substring ab or ba, so it cannot be in the form a^{n}b^{n}a^{n}.

Hence, uv^{2}xy^{2}z ? L.

**There is contradiction in both the cases, so L is not context free language.**