The language accepted by Finite Automata is known as Regular Language. Pumping Lemma is used to prove that a Language is not Regular. It cannot be used to prove that a language is Regular.

What is Pumping Lemma?

The term Pumping Lemma is made up of two words:-

Pumping: The word pumping refers to generating many input strings by pushing a symbol in an input string repeatedly.

Lemma: The word Lemma refers to the intermediate theorem in a proof.

There are two Pumping Lemmas, that are defined for

Regular Languages

Context-Free Languages

Let’s now learn about the Pumping Lemma in Theory of Computation in-depth.

Pumping Lemma For Regular Languages

Theorem: If A is a Regular Language, then A has a Pumping Length ‘P’ such that any string ‘S’ where |S ≥ P may be divided into three parts S = xyz such that the following conditions must be true:

1.) xy^{i}z ∈ A for every i ≥ 0

2.) |y| > 0

3.) |xy| ≤ P

In simple words, if a string y is ‘pumped’ or insert any number of times, the resultant string still remains in A.

Pumping Lemma is used as proof of the irregularity of a language. It means, that if a language is regular, it always satisfies the pumping lemma. If at least one string is made from pumping, not in language A, then A is not regular.

We use the CONTRADICTION method to prove that a language is not Regular.

Steps to prove that a language is not Regular using Pumping Lemma:

Step 1: Assume that Language A is Regular.

Step 2: It has to have a Pumping Length (say P).

Step 3: All strings longer than P can be pumped |S| ≥ P.

Step 4: Now, find a string ‘S’ in A such that |S| ≥ P.

Step 5: Divide S into x y z strings.

Step 6: Show that xy^{i}z ∉ A for some i.

Step 7: Then consider how S can be divided into x y z.

Step 8: Show that none of the above strings satisfies all three pumping conditions simultaneously.

Step 9: S cannot be pumped == CONTRADICTION.

Let’s apply these above steps to check whether a Language is not Regular with the help of Pumping Lemma.

Implementation of Pumping lemma for regular languages

Example: Using Pumping Lemma, prove that the language A = {a^{n}b^{n} | n≥0} is Not Regular.

Solution: We will follow the steps we have learned above to prove this.

Assume that A is Regular and has a Pumping length = P.

Let a string S = a^{p}b^{p}.

Now divide the S into the parts, x y z.

To divide the S, let’s take the value of P = 7.

Therefore, S = aaaaaaabbbbbbb (by putting P=7 in S = a^{p}b^{p}).

Case 1: Y consists of a string having the letter only ‘a’.

Case 2: Y consists of a string having the letter only ‘b’.

Case 3: Y consists of a string with the letters ‘a’ and ‘b’.

For all the above cases, we need to show xy^{i}z ∉ A for some i.

Let the value of i = 2. xy^{i}z => xy^{2}z

In Case 1. xy^{2}z = aa aaaa aaaa abbbbbbb

No of ‘a’ = 11, No. of ‘b’ = 7.

Since the No of ‘a’ != No. of ‘b’, but the original language has an equal number of ‘a’ and ‘b’; therefore, this string will not lie in our language.

In Case 2. xy^{2}z = aaaaaaabb bbbb bbbb b

No of ‘a’ = 7, No. of ‘b’ = 11.

Since the No of ‘a’ != No. of ‘b’, but the original language has an equal number of ‘a’ and ‘b’; therefore, this string will not lie in our language.

In Case 3. xy^{2}z = aaaa aabb aabb bbbbb

No of ‘a’ = 8, No. of ‘b’ = 9.

Since the No of ‘a’ != No. of ‘b’, but the original language has an equal number of ‘a’ and ‘b’, and also, this string did not follow the a^{n}b^{n} pattern; therefore, this string will not lie in our language.

We can see at i = 2 all the above three strings do not lie in the language A = {a^{n}b^{n} | n≥0}.

Therefore, the language A = {a^{n}b^{n} | n≥0} is not Regular.

Pumping Lemma for Context-free Languages

The Bar-Hillel lemma, also referred to as the pumping lemma for context-free languages, is a generalization of the pumping lemma for regular languages in formal language theory and computer science. It creates a characteristic that all context-free languages share. The pumping lemma can be used to show by contradiction that a particular language is not context-free. In contrast, other conditions must be met to guarantee that a language is context-free, such as Ogden's lemma or the Interchange lemma.

Implementation of Pumping lemma for Context-free Languages

Suppose a language L is context-free, then there will exist any integer p≥1, also called pumping length such that every string S in the context free language L which has a length of p or more can be written as :

s = uvwxy

with the substrings following the following property:

1.) uv^{n}wx^{n}y∈ L for every n ≥ 0

2.) |vx| ≥ 1

3.) |vwx| ≤ P

Applications of Pumping Lemma

Applying the Pumping Lemma will demonstrate that some languages are irregular. Never utilise a language to demonstrate its regularity.

Pumping Lemma is satisfied if L is regular.

L is not regular if it does not satisfy the Pumping Lemma.

Frequently Asked Questions

What is pumping lemma with example?

The Pumping Lemma is a tool in formal language theory that demonstrates the non-regularity of certain languages. For example, it shows that the language {0^n1^n} is not regular.

What is the formula for pumping lemma?

The Pumping Lemma for regular languages states that for any regular language L, there exists a pumping length p, such that any string s in L, where |s| ≥ p, can be divided into three parts, xyz, satisfying certain conditions. Specifically:

For all i ≥ 0, xy^iz must be in L.

|y| > 0

|xy| ≤ p

What is pumping lemma in CFL?

The Pumping Lemma for Context-Free Languages (CFL) is a tool in formal language theory that helps prove the non-context-freeness of certain languages by demonstrating they cannot satisfy pumping properties.

What is the logic of pumping lemma an example of?

The pumping lemma's logic exemplifies a fundamental principle used to prove that certain languages are not regular by demonstrating the impossibility of a finite automaton to account for all strings in the language.

Conclusion

In conclusion, the Pumping Lemma is a powerful tool in formal language theory that helps demonstrate the non-regularity of languages for regular grammars and the non-context-freeness of languages for context-free grammars. It highlights the limitations of these grammar types and is a valuable proof technique in formal language analysis.