Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Pumping Lemma?
3.
Pumping Lemma For Regular Languages
3.1.
Steps to prove that a language is not Regular using Pumping Lemma:
3.2.
Implementation of Pumping lemma for regular languages
4.
Pumping Lemma for Context-free Languages
4.1.
Implementation of Pumping lemma for Context-free Languages
5.
Applications of Pumping Lemma
6.
Frequently Asked Questions
6.1.
What is pumping lemma with example?
6.2.
What is the formula for pumping lemma?
6.3.
What is pumping lemma in CFL?
6.4.
What is the logic of pumping lemma an example of?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

What is Pumping Lemma?

Author Rajat Agrawal
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
What is Pumping Lemma?

Introduction

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.) xyiz ∈ A for every i ≥ 0

2.) |y| > 0

3.) |xy| ≤ P

In simple words, if a string 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 xyi 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 = {anbn | 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 = apbp.

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 = apbp).

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

Case 1

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

Case 2

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

Case 3

For all the above cases, we need to show xyi A for some i.

Let the value of i = 2.  xyiz => xy2

In Case 1. xy2z  = 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. xy2z  = 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. xy2z  = 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 anbn 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 = {anbn | n≥0}. 

Therefore, the language A = {anbn | 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.) uvnwxny∈ 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:

  1. For all i ≥ 0, xy^iz must be in L.
  2. |y| > 0
  3. |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.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like AmazonAdobeGoogle, etc. on Coding Ninjas Studio.

Previous article
DFA to Regular Expression Conversion
Next article
Regular Grammar
Live masterclass