FOR FREE YEAR SOLVED

Pumping Lemma:

Introduction:

We discuss pumping lemma for regular language, context-free language, and linear language.

1. If one language is Regular then it satisfies the pumping lemma for Regular.

2. If language is Context - free then it satisfies the pumping lemma for CFL.

3. If language is Linear Language then it will satisfy the pumping lemma for Linear Language.

All the theorems for pumping lemma are different for Regular Language, Context Free Language, Linear Language.

To prove a language is Regular or not we can’t use Pumping Lemma, some non-regular language that also satisfies $\mathbf{P}\mathbf{ }\mathbf{.}\mathbf{ }{\mathbf{L}}_{\mathbf{REG}}$.

“A language is not regular” “Given language is not a regular language”, we can prove by Pumping Lemma i.e. disproof, that if a language does not satisfy Pumping Lemma for regular then it must not be a regular language. 

We use pumping lemma only for disproof.

Pumping Lemma concept is coming from pigeonhole principal:

Now what is Pigeonhole Principal:

Let we have n pigeon and m pigeon hole and n > m then at least one of the pigeon hole will contain more than one pigeon.

Let we have three pigeon hole.

Case 1:

4 pigeons in a hole and others are empty which is also valid because we can say one of the pigeon holes will contain more than one pigeon. So, hole 1 or hole 2, or hole 3 contain all pigeons.

Case 2: Worst case: Equally distributed pigeon in all holes.

So, at least one pigeon hole contains more than one pigeon. So, hole 1 or 2 or 3 contain two pigeons.

In case of DFA/NFA we consider Pigeonhole Principal:

One symbol has two states ${\mathbf{q}}_{\mathbf{1}}\mathbf{ }\mathbf{a}\mathbf{ }{\mathbf{q}}_{\mathbf{2}}$ and two symbols have three states ${\mathbf{q}}_{\mathbf{1}}\mathbf{ }\mathbf{a}\mathbf{ }{\mathbf{q}}_{\mathbf{2}}\mathbf{ }\mathbf{b}\mathbf{ }{\mathbf{q}}_{\mathbf{3}}$ DFA.

Let us assume a string ω = abbba so, this string contains 5 symbols, accepted by the above machine.

Now string ω with 5 symbols should require 6 states to represent it as DFA/NFA.

But the above machine which accepted this given string has 3 states. 

So, we can say at least one state is there where it contains loop or this string is repeated in this DFA/NFA.

So, this is Pigeonhole principal base. And this loop is called pumping where we pumping this state ${\mathbf{q}}_{\mathbf{2}}$. That is why it is called Pumping Lemma.

One important thing is we are only discusses pumping lemma for infinite languages because it is only valid for infinite languages.

Because if it is finite then we never get any loop at any state or we never pump any state. So, that is why it is only valid for infinite language.

Let take an example of an infinite language where we pump any state.

Example:

Here we are pumping two states ${\mathbf{q}}_{\mathbf{1}}$and ${\mathbf{q}}_{\mathbf{2}}$ .

So, we are using this theorem to prove that one language is not regular. We never proof one language is regular or not from pumping lemma.

If one language does not satisfy pumping lemma then it is not regular.

For finite language, we never apply pumping lemma because all finite language is definitely regular.