Applying the pumping lemma

Theorem 4.2   The language $L=\{ 0^n1^n \mid n\in \mathbb{N}\}$ is not regular.

Proof: Assume $L$ would be regular. We will show that this leads to contradiction using the pumping lemma.

Now by the pumping lemma there is an $n$ such that we can split each word which is longer than $n$ such that the properties given by the pumping lemma hold. Consider $0^n1^n\in L$, this is certainly longer than $n$. We have that $xyz=0^n1^n$ and we know that $\vert xy\vert\leq n$, hence $y$ can only contain as, and since $y\not=\epsilon$ it must contain at least one a. Now according to the pumping lemma $xy^0z\in L$ but this cannot be the case because it contains at least one a less but the same number of bs as $0^n1^n$.

Hence, our assumption that $L$ is regular must have been wrong.

$\Box$

It is easy to see that the language

$$\{ 1^n \mid \textrm{$n$ is even} \}$$

is regular (just construct the appropriate DFA or use a regualr expression). However what about

$$\{ 1^n \mid \textrm{$n$ is a square}\}$$

where by saying $n$ is a square we mean that is there is an $k\in\mathbb{N}$ s.t. $n=k^2$. We may try as we like there is no way to find out whether we have a got a square number of $1$s by only using finite memory. And indeed:

Theorem 4.3   The language $L=\{ 1^n \mid \textrm{$n$ is a square} \}$ is not regular.

Proof: We apply the same strategy as above. Assume $L$ is regular then there is a number $n$ such we can split all longer words according to the pumping lemma. Let's take $w=1^{n^2}$ this is certainly long enough. By the pumping lemma we know that we can split $w=xyz$ s.t. the conditions of the pumping lemma hold. In particular we know that

$$1 \leq \vert y\vert \leq \vert xy\vert \leq n$$

Using the 3rd condition we know that

$$xyyz \in L$$

that is $\vert xyyz\vert$ is a square. However we know that

$$n^2 = \vert w\vert$$

$$ = \vert xyz\vert$$

$$ < \vert xyyz\vert \quad \textrm{since $1 \leq \vert y\vert$} = \vert xyz\vert + \vert y\vert$$

$$ \leq n^2 + n \quad \textrm{since $\vert y\vert\leq n$}$$

$$ < n^2 + 2n + 1$$

$$ = (n+1)^2$$

To summarize we have

$$n^2 < \vert xyyz\vert < (n+1)^2$$

That is $\vert xyyz\vert$ lies between two subsequent squares. But then it cannot be a square itself, and hence we have a contradiction to $xyyz \in L$.

We conclude $L$ is not regular. $\Box$

Given a word $w\in\Sigma^*$ we write $w^R$ for the word read backwards. I.e. $\textrm{abc}^R = \textrm{bca}$. Formally this can be defined as

$$\epsilon^R = \epsilon$$

$$(xw)^R = w^Rx$$

We use this to define the langauge of even length palindromes

$$L_{\textrm{pali}} = \{ ww^R \mid w\in\Sigma^*$$

I.e. for $\Sigma=\{a,b\}$ we have $\textrm{abba}\in L_{\textrm{pali}}$. Using the intuition that finite automata can only use finite memory it should be clear that this language is not regular, becasue one has to remember the first half of the word to check whetherthe 2nd half is the same word read backwards. Indeed, we can show:

Theorem 4.4   Given $\Sigma=\{\textrm{a},\textrm{b}\}$ we have that $L_{\textrm{pali}}$ is not regular.

Proof: We use the pumping lemma: We assume that $L_{\textrm{pali}}$ is regular. Now given a pumping number $n$ we construct $w=0^n110^n\in L_{\textrm{pali}}$, this word is certainly longer than $n$. From the pumping lemma we know that there is a splitting of the word $w=xyz$ s.t. $\vert xy\vert\leq n$ and hence $y$ may only contain 0s and since $y\not=\epsilon$ at least one. We conclude that $xz\in\L _{\textrm{pali}}$ where $xz = 0^m110^n$ where $m<n$. However, this word cannot be a palindrome since only the first half conatains any $1$s.

Hencce our assumption $L_{\textrm{pali}}$ is regular must be wrong. $\Box$

The proof works for any alphabet with at least 2 different symbols. However, if $\Sigma$ contains only one symbol as in $\Sigma=\{1\}$ then $L_{\textrm{pali}}$ is the laguage of an even number of $1$s and this is regular $L_{\textrm{pali}}=(11)^*$.