Proving that $\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular using the pumping lemma.

Question

I need to prove that $L=\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular. First of all I assume that L is regular. Then L satisfies the pumping lemma, so let p be the pumping length. I've tried several strings, like $a^pbba^p$ that work with the palindrome language ($ww^r$), but the last $x \in \{a,b\}^+$ makes it harder to prove, because it can actually be anything after a palindrome in this string. Any hints for choosing the string to be pumped?

Edit: I think the way to solve this is after pumping to end with a string $ww^r$ so $x=\epsilon$ (and then obviously $ww^r \notin L$) but I can't find any.

Answer 1

Completely revised.

It appears that the pumping lemma isn’t going to help here.

Let $s=ww^Ru\in L$ be such that $|w|\ge\max\{p,2\}$. Without loss of generality we may take $a$ to be the first character of $w$. If $s=xyz$ is the decomposition of $s$ guaranteed by the pumping lemma, it could happen that $x$ is empty, and $y=a$. Then $xy^kz\in L$ for $k\ge 2$, since it begins $aa$ and has length greater than $2$, and of course $xyz\in L$ by hypothesis. Finally, if $w=av$, then

$$xy^0z=z=vv^Rau\in L\;,$$

since $v$ and $au$ are both non-empty. Thus, $xy^kz\in L$ for each $k\ge 0$.

Added: We can, however, use the Myhill-Nerode theorem to show that $L$ is not regular. For each $n\in\Bbb Z^+$ let $w_n=aba^2b^2\ldots a^nb^n$. If $1\le m<n$, the string $w_m^Rb$ is a distinguishing extension for $w_m$ and $w_n$: $w_mw_m^Rb\in L$, and $w_nw_m^Rb\notin L$. Thus, $L$ has infinitely many Myhill-Nerode equivalence classes and cannot be regular.

Answer 2

The pumping lemma won't help because it may be the case that $p\ge4$.

To see that all proofs by direct application of the pumping lemma fail: Assume there is a test word is $ww^Ru\in L$ that can be used in the pumping lemma.

• If $|w|>1$, say $w=\alpha v$ with $\alpha\in \{a,b\}$, then we can let $x=\epsilon$, $y=\alpha$, $z=vw^Ru=vv^R\alpha u$. Note that $|xy|=1< p$, $|y|\ge 1$, $|z|\ge 4$, $|v|\ge1$. Then $xz=vv^R\alpha u\in L$, $xyz=ww^Ru\in L$, and for $k\ge2$ we have $xy^kz=\alpha\alpha^Ry^{k-2}z\in L$.
• If $|w|=1$, then $|u|>1$ as $|ww^Ru|\ge p\ge 4$, say $v=\alpha u$. Let $x=ww^R$, $y=\alpha$, $z=u$. Then $xy^kz=ww^R\alpha^ku\in L$ for all $k\ge0$.

Answer 3

I don't think you can show that $L$ is not regular using the Pumping Lemma. That is, there is a $p$ such that every string in $L$ of length at least $p$ has a "pumpable decomposition".

Let $p = 4$, and suppose that $s$ is any string in $L$ of length at least $p$. Then there are nonempty strings $w,x$ such that $s = ww^Rx$

• Case 1. If $w$ has length $1$, take $t = ww^R$, $u$ the first symbol of $x$, and $v$ the rest of $s$ (which is nonempty). (Note that $|tu| = 3 \leq p$.) Then for any $k \geq 0$ we have that $tu^kv = ww^Ru^kv$ is in $L$.

• Case 2. If $w$ has length at least $2$, take $t = \epsilon$, $u$ the initial symbol in $w$ (also the initial symbol of $s$), and let $v$ be the rest of $s$. (Note that $|tu| = 1 \leq p$.) I claim that $tu^kv$ is in $L$ for all $k \geq 0$. Without any real loss of generality, assume that $u = a$, so $w = az$ for some nonempty string $z$. Then $v = zz^Rax$.

  • For $k = 0$, we have $tu^kv = v = zz^Rax$, which clearly belongs to $L$.

  • For $k = 1$, clearly $tu^kv = s$ belongs to $L$.

  • For $k \geq 2$, we have that $tu^kv = a^kv = a^kzz^Rax$. This belongs to $L$ by taking the witnessing $w$ to be $a$, and the witnessing $x$ to be $a^{k-2}zz^Rax$.