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

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.

• Also, I know this language is context-free but regular languages are a subset of the context-free languages and I'm looking to prove that this language is context-free but not regular. – mcnnowak Aug 18 '13 at 21:42
• But the regular languages are not closed under reversing, as indeed $A$ shows, as proven in your theorem! $\{ww^R \mid w \in \Sigma^*\}$ is regular if and only if $|\Sigma|=1$. – Pål GD Aug 18 '13 at 23:06
• Do you confuse this with the following? Let $A$ be a regular language. Then $A^R$ is also regular, where $A^R = \{w^R \mid w \in A\}$? That is, reverse every string in $A$ and you have a regular language as well. – Pål GD Aug 18 '13 at 23:09
• Let me stress that your proof is wrong as stated. You need to come up with a word $w$ so that $xw^R$ cannot be written as $kk^R$. As mentioned by Pål, this will be impossible if $|\Sigma|=1$. – Yuval Filmus Aug 19 '13 at 1:16
• You are not allowed to pick the division of your string! – vonbrand Feb 10 at 16:01

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

• A is correct, B is wrong. Suppose for example that $w = abaa$ and $x = ab$; we get $xw^R = abaaba = zz^R$ for $z=aba$. – Yuval Filmus Aug 19 '13 at 0:18
• That is actually what I mean. You can't use $xw^R$ in the pumping lemma unless you know it it's in the language. Since $xw^R$ is generated through the pumping lemma, it can only be in the language if the language is regular. Therefore, you can't use $xw^R$ to prove that the language is regular. (It would be circular reasoning.) The entire thing with $xw^R$ is a red herring. In fact, it looks to me like he proves the language is irregular before ever reaching that point. I'll see about clarifying my answer. – Nobbynob Littlun Aug 19 '13 at 0:28
• Andrew, you're getting your logic wrong. You're assuming that the language is regular, and then you find a contradiction with the switching lemma. The switching lemma states that if some word $v$ is in the language, then a bunch of other words $V$ are in the language. In order to obtain a contradiction, you arrange that $v$ is in the language, but one of the words in $V$ isn't. In our case, $v = ww^R$, and you need to arrange that $xw^R \in V$ isn't in the language. – Yuval Filmus Aug 19 '13 at 0:31
• Woah, slow down buddy! I think you're misreading. I'm saying his pumping lemma alone is enough to show contradiction: the language is not regular. Switching lemma? I don't even get into that. He thinks there's a problem, and can't find it. But his trouble is in understanding what happens when you concatenate languages. I'll say it plainly: The $xw^R=xw^R$ business is a red herring. No help at all. We can ignore it completely and have an answer. – Nobbynob Littlun Aug 19 '13 at 0:43
• @Raphael, unfortunately the comments are not obsolete. This answer (first part) is wrong. – Yuval Filmus Aug 22 '13 at 19:49

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.

• You don't need to intersect it with $a^*bba^*$. Just take $n$ larger than the pumping length. – Yuval Filmus Aug 19 '13 at 16:32
• @yuval-filmus I don't get your argument. If you just apply the pumping lemma to $a^nbba^n$, you may have $bb$ as a pumping factor, but $a^n(bb)^*a^n \subset L$. I probably missed something. – J.-E. Pin Aug 19 '13 at 18:15
• The pumping lemma assures you that the pumped part is within the first $p$ symbols, where $p$ is the size of the minimal DFA for the language. Other versions allow even more control, but that's enough here. If $n \geq p$ then the pumped part is inside the first $a^n$, so you can guarantee to avoid the problematic $a^n(bb)^*a^n$. – Yuval Filmus Aug 19 '13 at 18:26
• @yuval-filmus Ooops. You're right of course. – J.-E. Pin Aug 19 '13 at 19:39

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.