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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.