# Using the Pumping Lemma To Prove A Language Is Not Regular

I am taking a Automata class and we just went over the Pumping Lemma. Initially, it did not make sense. I am still not fully comfortable but I have started trying to use it to prove that a language is not regular.

If anyone can look over my attempt at using the Pumping Lemma and let me know if I am using it correctly, I'd really appreciate it. Any pointers or advice is welcome.

For $\Sigma=\{a,b\}$, $L=\{ww^R:w\in\Sigma^*\}$ is not regular.

Let $L=\{ww^R:w\in\Sigma^*\}$. Assume $L$ is regular. Let $m$ be the number from the pumping lemma. Let $s=a^mbba^m$. Since $s\in L$ and $|s|\ge m$, the pumping lemma must apply. Specifically, $s=xyz$, where $y\ne\lambda$, and $|xy|\le m$. Then

• $y=a^k$, where $0<k\le m$;
• $x=a$, where $0\le q<m$; and
• $z=bba^{m-k}$.

The pumping lemma says that $xyyz\in L$.

\begin{align*} xyyz&=aa^ka^kbba^{m-k}\\ &=abba^{k+\underline k+m-\underline k}\\ &=abba^k+m\notin L\;. \end{align*}

Thus, our assumption that $L$ is regular must not be true. Thus, $L$ must not be regular.

## 1 Answer

There are several problems here, though the choice of $s$ is sound. First, I suspect that you meant that $x=a^q$, though the $q$ is missing both in the definition of $x$ and later in the expansion of $xyyz$. In that case you might as well say that $x=a^{m-k}$. Next, the definition of $z$ is simply wrong: $z=bba^m$. Now the pumping lemma says that $xy^2z\in L$, where

$$xy^2z=a^{m-k}a^{2k}bba^m=a^{m+k}bba^m\notin L\;,$$

since $k>0$, and you get the desired conclusion.

More generally,

$$xy^\ell z=a^{m-k}a^{\ell k}bba^m=a^{m+(\ell-1)k}bba^m$$

is in $L$ if and only if $\ell=1$, so any pumping of $s$ up or down takes you out of $L$.