Is the language that accepts strings concatenated with their reverse regular?

Question

If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\Sigma^*\}$$ for some input alphabet $\Sigma$, also regular? If not, why not?

I've been trying to find a proof for this using the pumping lemma, but it seems that selecting any substring towards the middle of the string being pumped could also be of the form $\{ww^R|w\in\Sigma^*\}$, causing the original string to remain in its original form.

Here's a try:

$\textbf{Theorem:}$ The language, $A$, generated by $\{ww^R|w\in\Sigma^*\}$ is not regular.

$\textbf{Proof:}$ Assume $A$ is regular (We will use the Pumping Lemma for Regular Languages to show a contradiction). Let the input string $s$ be $ww^R$ and let $p = |w|$.

When splitting $s$ into substrings $x, y, z$ such that $s=xyz$ we see that $xy$ must be a substring of $w$ by the third condition of the Pumping Lemma ($|xy|\le p$).

By the first condition of the Pumping Lemma, we see that all strings of the form $xy^iz$ must be in $A$ for all $i \ge 0$. Taking $i$ to be zero, we obtain the string $xw^R$. $|x| < |w^R|$ so $xy^0z \notin A$.

QED? What if $xw^R$ can still be split so that for some substring $k$, $kk^R = xw^R$?

I think I may be overthinking this but it's really bugging me.

Answer 1

You're over-thinking it on the $xw^R=ww^R$ thing, that's a red herring. But you're not over-thinking it by looking for a contradiction, you're looking in the wrong place.

First, your proof that the language is irregular is correct. You're aiming to show a contradiction. All you need is one counterexample; just one! And you found it already. This may seem paradoxical, but your understanding of how to operate on languages is a little off. As you noted, regular languages are closed under reversal:

$L^R = \{w^R|w\in L\}$

They are also closed under concatenation:

$L\circ L^R = \{wv|w\in L, v\in L^R\}$

But, you see, that's a little different from $L_{mirrored} = \{ww^R|w\in L\}$. Look:

$L = \{$ cat, dog$\}$

$L^R = \{$ tac, god$\}$

$L\circ L^R = \{$ cattac, catgod, dogtac, doggod$\}$

$L_{mirrored} = \{$ cattac, doggod$\}$

There's your contradiction! You must have thought those last two were the same, when they're not. Rather,

$L_{mirrored} \subseteq L\circ L^R$

And the subset of a regular language is not necessarily regular.

edit: I removed a large chunk of this answer, so the comments below will probably be confusing...

Answer 2

Here is a short solution. Let $L = \{ uu^r \mid u \in A^*\}$. If $A$ is empty or contains only one letter, then $L$ is regular. Suppose now that $A$ contains at least two letters, say $a$ and $b$. Using the pumping lemma, it is easy to see that the language $L \cap a^*bba^* = \{a^nbba^n \mid n \geqslant 0 \}$ is not regular. Therefore $L$ is not regular, since the intersection of two regular languages is regular.

Answer 3

Hint: Find a word $w$ so that for every proper substring $x$ of $w$, $xw^R$ is not of the form $zz^R$. As mentioned by Pål, you will only be able to find $w$ if the alphabet contains at least two letters. Also, naturally $w$ must depend on the pumping length $p$ (since your argument relies on $|w| \geq p$).

Not every word $w$ works, so your proof isn't complete. You have identified this problem yourself. Every step in a proof needs to be justifiable, otherwise it's not a proof. If there is a step you're not sure about, then it's not a proof.