pumping lemma: ww^R not regular
Matthew Barrera 
I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma.
Let $p$ be the pumping length and $s = a^pbba^p$.
$x = \epsilon$, $y = a^p$, $z = bba^p \implies s = \epsilon a^p bba^p = a^pbba^p$
1) Was $s$ properly divided?
Let's see:
$|xy| \leq p$
$|y| > 0$ (I'm not sure about this since $|y|$ depends on $p$?)
If we take $i = 2$, $xyyz = \epsilon a^p a^p bba^p \notin L$, so $L$ is not regular.
2) What about $i = 0$? $xz = \epsilon bba^p \notin L$, so $L$ is not regular.
$\endgroup$ 13 Answers
$\begingroup$The hard part about these kinds of arguments is getting the quantifiers right. The pumping lemma says:
If $L$ is regular, then there exists a $p \ge 1$, such that for all $w \in L$ with $|w| \ge p$, there exists a "splitting" $w = xyz$, such that for all $i \ge 0$, $xy^iz \in L$.
You can think of this as an adversarial game. You pick a $p$, your opponent picks a $w$, you pick the $xyz$, they pick the $i$. If you can show it's in $L$, you win. So, the pumping lemma can be thought of as: if $L$ is regular, you can always win this game.
Therefore, if you lose, the language is not regular. So let's switch the roles; you are now the aggressor. Your opponent picks a $p$, you pick a $w$, they pick a splitting, you pick an $i$, and if you can always win, then $L$ is not regular. This can be phrased more mathematically: (note that the quantifiers are now switched!)
Let $L$ be a language. If for all $p \ge 1$, there exists a $w \in L$ with $|w| \ge p$, such that for all "splittings" $w = xyz$, there exists an $i \ge 0$ such that $xy^iz \notin L$, then $L$ is not regular.
So when proving languages are not regular, you don't get to pick how it splits!
What we have to do is pick our $w$ very carefully. I'll phrase this as a game first, then as a proof.
Let your opponent pick $p$. We'll choose $w = a^pbba^p$. No matter how our opponent splits the string, the conditions of the game/lemma require that $|xy| \le p$. So $xy$ consists only of $a$s, and cannot contain the $b$s. We choose $i = 0$, which will cause the $a$s to be asymmetric, and $xz \notin L$.
Assume $L$ is regular, for the sake of contradiction. Then $L$ satisfies the pumping lemma, so let $p$ be the pumping length. Consider $w = a^pbba^p$, where $a, b \in \Sigma$, $a \ne b$. Since $|w| = 2p + 2 \ge p$, there is some splitting $w = xyz$ satisfying the lemma. Since we know $|xy| \le p$, it must be that $x = a^k$ and $y = a^\ell$, with $k + \ell \le p$ and $\ell > 0$. This means that $z = a^{p-k-\ell} bb a^p$. Let $i = 0$, which gives $xz = a^{p - \ell} bb a^p$, which is not in $L$. By contradiction, $L$ is irregular.
By "splitting", I mean strings $x$, $y$, $z$ in $\Sigma^\ast$ such that $w = xyz$, $|xy| \le p$, and $|y| > 0$.
$\endgroup$ 6 $\begingroup$Note that this is true only if $|\Sigma|>1$, since for $|\Sigma|=1$, the language would just be $\Sigma^*$, which is regular.
Given a $|\Sigma|>1$, assume that $L=\{ ww^R|w\in\Sigma^*\}$ is regular and let $p$ be it's pumping length.
Consider the string $w^2(w^R)^2\in L$ where $|w|\geq 1$, $|ww|\leq p$ and $w\notin L$. This is all easily possible you chose a pumping length $p\geq 4$
Now write it as $xyz$ where $x=y=w$ and $z=(w^R)^2$.
Now pump up once to get $w^3(w^R)^2\in L$, which contradicts the definition of $L$.
We must therefore conclude that $L$ is not regular.
$\endgroup$ 1 $\begingroup$Assume that L is regular.
Consider any pumping lemma constant k (note: k is a positive integer so $k>=1$). Now consider a string s=$a^m$$b^m$$b^m$$a^m$ where $m>=1$
Now consider any decomposition of this string. It will be of the form $s=xyz$ where y will be of the form y = $a^j$ where $1<=j=k$ . Now by pumping lemma, $xv^ik$ belongs to L for all $i>=0$. Consider i=0, then we have the string of the form $a^lb^ma^mb^m$ where $l<m$. Since the number of a's in the left side of the string is less than the number of a's in the right part of the string, it can never be represented as $ww^R$ where $w∈${a,b}$^*$. So this violates our assumption that L is regular
We have by contradiction that L is not regular
$\endgroup$
