Pumping Lemma for Regular Languages

The pumping lemma states that if a language is regular, then it can be pumped.

For example, let's say we have a language $L=a{b}^{\ast }a$. Then it's clear that $b$ can be pumped 0 to infinity times. So $aa$ would be in the language, and so would $abbbbbbbba$.

First, if a language is a regular language, then you should be able to split a string of length $p$ ($|s|\ge p$) in the language into three parts: the initial part, the repeated part, and the final part.

The first constraint states that for any string $s=xyz$, if we repeat the middle part $y$, the new strings formed by this repetition ($x{y}^{i}z$ for all $i\ge 0$) should still belong to the language $L$.

The second constraint, $|y|\ge 1$, emphasizes that the repeated section $y$ must be of length at least one, meaning it must contain at least one character. After all, you can't pump the empty string $ϵ$.

The third constraint, $|xy|\le p$, ensures that the length of the initial part and the repeated part together must be less than or equal to the pumping length. More importantly, it also says that $y$ is at least within $p$ distance from the start of the string.

Proving Regularity

The pumping lemma is more useful when we factor in the contrapositive to prove that some language is not regular. Our pumping lemma makes the statement that if a language is regular, then it is pumpable.

If this, then that.

The following contrapositive is a logically equivalent statement (unlike inverses and converses).

If not that, then not this.

This means that we can use the pumping lemma in a proof of contradiction to show that a certain language is not regular by showing that it cannot be pumped.

To prove that a language $L$ is not regular, we need to use the proof by contradiction. We can do this by following the following steps:

1. Assume $L$ is regular.
2. Let $p$ be the pumping length given by the pumping lemma.
3. Choose a string that has at least length $p$.
4. Break the string down into some $xyz$ such that $|xy|\ge p$ and $|y|>0$.

Example: Proving that $L=\{a^n{b}^n\mid n\ge 0\}$ is Irregular

Step 1 and 2 are just formalities. We begin the proof by saying, "Let's assume $L$ is regular." Then we follow up by saying, "Let $p$ be the pumping length given by the pumping lemma."

Step 3 is carefully crafting a string that is a part of the language that is at least length $p$.

Step 4 is the verbose part where we satisfy all of the constraints given in the pumping lemma and using it to a show a contradiction.

Let's assume L is regular.

The pumping lemma states that f $L$ is a regular language, then there is a number $p$ where if $s$ is any string in $L$ of length at least $p$, then $s$ may be divided into three pieces, $s=xyz$, satisfying the following conditions:

1. $x{y}^{i}z\in L$ for all $i\ge 0$
2. $|y|\ge 1$
3. $|xy|\le p$

Let's use the string $s=a^p{b}^p$. We can see that $|s|\ge p$ and $s\in L$.

Since condition 3 states that $|xy|\le p$, $xy=a^p$. Therefore, $x=ϵ$ and $y=a^p$. Then we can split the string to $x=ϵ$, $y=a^p$, and $z=b^p$.

Condition 1 states that we should be able to pump $y$ $i$ times with it staying in the language, but we can see that this is contradictory with the counterexample $s=a^i{b}^p=a^0{b}^p=b^p$ such that $i=0$.

Therefore, L is not a regular language.