Pumping Lemma for Context Free Languages

In this class, We discuss Pumping Lemma for Context-Free Languages.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of pumping lemma for regular languages. Click Here.

First, refresh the concept of pumping lemma for regular languages.

Along with the concept, we come into pumping lemma for context-free languages.

The language aⁿbⁿ is a context-free language, and it is not a regular language.

Why is aⁿbⁿ not a regular language?

In the language L = aⁿbⁿ we count the equivalence of a and b.

Counting is not possible in finite automata because we do not have memory in finite automata.

But in context-free languages, we had a stack memory. So we can check the equivalence count.

To prove the given language is not regular. We followed as below.

Take input string aaabbb.

We divide the string into x(y)ⁱz. We have taken aa(a)ⁱbbb.

We keep on pumping y.

We need to generate the strings present in the language L.

In the above example, we keep on pumping a.

As i value increases, a’s are increasing.

Regular languages can not do equivalence count for two variables. So we have taken a single pumping variable.

For the same language, if we divide the string into five parts.

The below example shows two pumping variables.

Example: Take aaabbb.

Divide the string as u(v)ⁱw(x)ⁱy.

a(a)ⁱa(b)ⁱbb

For i = 1 we get aaabbb

For i = 2 we get aaaabbbb

If we take two pumping variables, we can not prove the given language does not belong to the regular language.

The context-free languages can do equivalence of two symbols.

The language L1 = aⁿbⁿcⁿ is not a context-free language.

The language L1 is doing an equivalence count of three symbols, and we can not do this using two pumping variables.

So to prove the language is not a context-free language, we choose two pumping variables.

Pumping Lemma: We use a pumping lemma to show the given language is not a Context-Free Language.

We divide the given input string into five parts. u(v)ⁱw(x)ⁱy.

We follow the conditions.

1) |vx| >= 0

2) |vwx| <=n

The first condition says you do not take epsilon for variables v and x.

No use if we take epsilon for both pumping variables.

The middle string vwx should be less than or equal to n.

We can take any n value.

To make the middle part as short as possible, we chose the n value.

Take n = 3.

The input string is aaabbbccc.

With n=3, The middle part vwx can take different possibilities.

The middle part vwx can take only a’s or only b’s or c’s, a combination of a and b, or a combination of b and c.

The above possibilities are enough to show that the given language is not context-free.

Possibility 1: a(a)ⁱa(b)ⁱbb

For i = 1 we get aaabbbccc

For i = 2 we get aaaabbbbccc

For i =2, we did not get the string present in our language

Possibility 2: aaab(b)ⁱb(c)ⁱcc

For i = 1 we get aaabbbccc

For i = 2 we get aaabbbbcccc

For i =2, we did not get the string present in our language.