Pumping Lemma for Regular Grammars
Pumping Lemma is applied to infinite languages to show that languages are not regular. It should never be assured that a language is regular.
| V.Important: Keep in mind all finite languages are regular, and there is no need to check whether they are regular or not, but all infinite languages are not Regular languages as a^n, b^n is an infinite language but not a regular language. |
Conditions of Pumping Lemma
There are three conditions for pumping lemma. Suppose an infinite language (L) with string W = anb2n. See in string W; the string length is greater than or equal to “n.” “n” is a pumping length.
Let’s divide the string into three parts, i.e., w = xyz. Pumping length conditions are given below.
- For all i ≥ 0, the string xyiz is also in L. Here “i” is used to pump “y” value
- |y| > 0
- |xy| ≤ c
If the string (w = xyz) fails any condition, it will declare itself a non-regular language.
We can say
- If infinite Language (L) does not satisfy all three conditions of Pumping Lemma, then it will be a non-regular language.
- If given infinite Language satisfies all three conditions of Pumping Lemma, then it may or may not be a regular language.
| Tip: The pumping lemma gives the result of the failure of any condition. That’s why it is also called a negative test. |
Example of Pumping Lemma
Suppose a string W = anb2n, which belongs to language L. See in string W, the length of the string is greater than or equal to “n”. It satisfies the pumping theorem and now checks three conditions.
The above string (W = anb2n) says that infinite language will hold double the number of “b” as compared to “a”. If n=2, then string = aabbbb
Now divide the above string into 3 parts
- X= a (first “a” from string, any part from string can be given to X, Y, Z)
- Y= abbb ( second, third, fourth, and fifth)
- Z=b (last value)
According to the first condition, consider the value of i=2, which will generate the following result.
W= a(abbbabbbb)b // y pump to double
Now check the pump string, which does not belong to the language because the original string was “string (W = anb2n), which said that infinite language will hold double the number of “b” as compared to “a”.
As the first condition fails, it is not a regular language.
