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

Problem Detail: 

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.

Asked By : mcnnowak

Answered By : AndrewK

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13804