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