# 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 = a ^{n}b^{2n}**. 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 xy
^{i}z 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 = a^{n}b^{2n}) 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.**