What is pumping lemma?

Pumping lemma for regular languages

The pumping lemma is a property of a regular languageA formal language which can be expressed with a regular expression.. It is used to prove the non-regularity of certain languages.

Regular languages always satisfy the pumping lemma. However, if the pumping lemma is satisfied, the language does not need to be regular.

Note: This is only useful for infinite languages since all finite languages are regular.

Theorem

In simple terms, this theorem states that if $L$ is a regular language ∃ (there exists), a FA of $p$ states holds string $s ∈ L$. Then, for all strings $s ∈ L$, with $|s| ≥ p$, there exists a division of $s$ in three parts, i.e., $S= x.y.z$, such that the following three conditions are held:

• $|x.y| ≤ p$ (length of $x$ + length of $y$ is $≤ p$)
• $|y| != 0$ ( $x$,$z$ can be null, but $y$ cannot be null, and the length of $y ≥ 1$)
• $xy^iz ∈ L \ ∀ \ i ≥ 0$

Let's look at an example where the pumping lemma does not hold.

Example

Prove that $L_1= {a^nb^n | n ≥ 0 }$ is a non-regular language.

Applying Pumping lemma

Step 1: Assume that $L_1$ is a regular language with $p$ states to prove by contradiction.

Step 2: Taking a string s with $|s| ≥ p$,$s = a^pb^p$

Step 3: Dividing s into $x$, $y$, and $z$. There are three possible divisions for $y$ in this case.

  Case 1: $y$ gets only $a$'s from $a^p$

  Case 2: y gets only $b$'s from $b^p$

  Case 3: y gets some $a$'s and some $b$'s from $a^p b^p$

Step 4: Pumping the $y$ substring.

  Case 1:

  Case 2:

  Case 3:

Because there is a contradiction in every case, we conclude that $L_1$ is not regular, and the pumping lemma does not hold.

Now, let's look at an example where the pumping lemma holds:

Example

Prove that $L_2$= {all string ending with $aba$} is a non-regular language.

Applying pumping lemma

Step 1: Suppose that $L_2$ is a regular language and take a FA with $p=8$

Step 2: Take a string $s$ with $|s| ≥ p$ , s ends with '$aba$'

Step 3: Divide $s$ into $x, y, z$

Step 4: Pump the $y$ substring such that:

As the new string still ends with $aba$, we can conclude that the pumping lemma holds, but it cannot be said that $L_2$ is regular or non-regular.