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ⁱxyⁱ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ⁱxyⁱz ? L. It contradicts our assumption and it is proved that given languages is not context free.

Example 1:

Let L= { aⁿbⁿcⁿ | 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ⁿbⁿcⁿ   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ⁿbⁿcⁿ

Let i = 2

Then we have uv²xy²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ⁿbⁿcⁿ  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²xy²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ⁿbⁿaⁿ | 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ⁿbⁿaⁿ   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²xy²z = a^n+k  b ^n+k a ⁿ  or a ⁿ b ^n+k  a^n+k   which is not in L.

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

Let, i = 2

Then uv²xy²z will have more than one substring ab or ba, so it cannot be in the form aⁿbⁿaⁿ.

Hence, uv²xy²z ? L.

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