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.) xyiz ∈ 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 xyiz ∉ 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 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 xyiz ∉ A for some i.
Let the value of i = 2. xyiz => xy2z
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:
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.
8+ registered 