2. Non-regular languages & Pumping Lemma

Example 1: $L=\{a^n{b}^n:n=0,1,2,\dots \}$

Our theorem is that the language $L=\{a^n{b}^n:n=0,1,2,\dots \}$ is not regular.

1. To begin to prove that it is not regular, we assume that it is regular and hence we know that The Pumping Lemma (Theorem) must hold.
2. Hence there is some $p$ such that every word in the language of length $|w|\ge p$ can be written in the form $w=xyz$.
3. Let’s substitute $n$ with $p$ to give us $w=a^p{b}^p$ which satisfies $|w|\ge p$.
4. Now we need to decompose $a^p{b}^p$ into $xyz$, we need to satisfy:
   1. $|xy|\le p$
   2. $|y|>0$ So that we can show $x{y}^{n}z\in L$ for all $n\ge 0$.
5. Let’s assume $x=a^{\alpha }$ ($\alpha \ge 0$) and $y=a^{\beta }$ ($\beta >0\because |y|>0$).
6. Let’s assume $z=a^{p-\alpha -\beta }{b}^p$. (the remainder of the word)
7. Since we have satisfied the two conditions, $x{y}^{n}z\in L$ must hold:

$$\begin{array}{rl}x{y}^{n}z& \equiv a^{\alpha }(a^{\beta }{)}^n{a}^{p-\alpha -\beta }{b}^p\\ & \equiv a^{\alpha }{a}^{\beta n}{a}^{p-\alpha -\beta }{b}^p\\ & \equiv a^{p+\beta n-\beta }{b}^p\end{array}$$

8. The only way this string would ever be in the language and hence $x{y}^{n}z\in L$ holds is if these two exponents are the same for all $n\ge 0$, so we can instead check if there is a condition where the exponents do not equal.

$$\begin{array}{rl}p+\beta n-\beta & \ne p\\ \beta n-\beta & \ne 0\\ \beta n& \ne \beta \\ n& \ne 1\end{array}$$

9. But we know that the exponents must equal for all $n\ge 0$, so if we pick say, $n=2$, then the exponents do not match, hence $x{y}^{n}z\in L$ does not hold. This is a contradiction which means the language given at the start is not regular.

The Pumping Lemma

The Pumping Lemma (Theorem)

The Pumping Lemma says if $L\subseteq {\Sigma }^{\ast }$ is a regular language then there is some $p>0$ such that every word $w\in L$ of length $|w|\ge p$ can be written in the form $w=xyz$ for $x,y,z\in {\Sigma }^{\ast }$ such that:

• If $|xy|\le p$ and $|y|>0$,
• then $x{y}^{n}z\in L$ for all $n\ge 0$.

Link to original

More Examples

https://www.youtube.com/watch?v=x2J5kaf6gjg&ab_channel=EasyTheory

Example 2: Prove $L=\{a^n{b}^m:n<m\}$ is not regular.

1. Assume that the language is regular and the Pumping Lemma holds.
2. Hence there is some $p$ such that every word in the language of length $|w|\ge p$ can be written in the form $w=xyz$.
3. Let’s assume $w=a^p{b}^p$ where $|w|\ge p$.
4. Decompose to satisfy $|xy|\le p$ and $|y|>0$:
   1. $x=a^{\alpha }$ ($\alpha \ge 0$)
   2. $y=a^{\beta }$ ($\beta >0\because |y|>0$)
   3. $z=a^{p-\alpha -\beta -1}{b}^p$ (we subtract one since $n$ is smaller than $m$)
5. Since we have satisfied the two conditions, $x{y}^{n}z\in L$ must hold:

$$\begin{array}{rl}x{y}^{n}z& \equiv a^{\alpha }{a}^{\beta n}{a}^{p-\alpha -\beta -1}{b}^p\\ & \equiv a^{p+\beta n-\beta -1}{b}^p\end{array}$$

6. This string may only be in the language and hence $x{y}^{n}z\in L$ holds if the exponent of $a$ is always smaller than the exponent of $b$ for all $n\ge 0$.

$$\begin{array}{rl}p+\beta n-\beta -1& <p\\ \beta (n-1)-1& <0\\ \beta (n-1)& <1\\ \beta & <\frac{1}{n-1}\end{array}$$

7. Since $n\ge 0$, we can pick $n=0$, which gives us:

$$\begin{array}{rl}\beta & <\frac{1}{-1}\\ \beta & <-1\end{array}$$

8. This is a contradiction as earlier we stated $\beta >0$ because $|y|>0$.
9. Hence by contradiction, this language is not regular.