pumping lemma: ww^R not regular

Question

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.

Answer 1

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

Answer 2

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.