# If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular? Explain.

Intuitively, I suspect that $L_1$ may be nonregular, since the set of even-length palindromes of an arbitrary regular language $L$ isn't necessarily regular. However, I'm not sure that the pumping lemma can be used to prove the non-regularity of $L_1$.

• Try the language $L=ab^*a$. – Shaull Oct 17 '14 at 21:04
• This would imply that $L_1 = b^*a$, which is regular. It seems that $L_1$, in general, is the set of second-halves of even length palindromes of $L$. – David Smith Oct 17 '14 at 21:27
• To get a non-regular language for $L_1$, my intuition is that $L \cap EPAL$ would need to be at least context-sensitive. Why? Because strings in the intersection would need to satisfy two distinct conditions, each requiring memory, simultaneously: they'd need to be even-length palindromes, and the second half would have to have some property that makes $L_1$ non-regular. However, from closure properties, we know that $L \cap EPAL$ is definitely context-free. So my guess would be that $L_1$ is always regular. Anyway, something to think about... there might be a solution farther down that road. – Patrick87 Oct 17 '14 at 21:48
• So, then, using your terminology, $L_1 = (1/2(L \cap EPAL))^R$, where $1/2(L)$ consists of the first halves of even-length strings of $L$. $1/2(L)$ I am certain is closed under the class of regular languages. – David Smith Oct 17 '14 at 21:55
• Yes, that looks right. In those terms, my observation is that $1/2(L)$ may be regular even if $L$ is not, and my intuition is that any subset $X$ of $EPAL$ for which $1/2(X)$ is non-regular must not be context-free. If I were to try to prove it, I'd make some sort of argument that a PDA couldn't remember enough to accept $w^Rw$ while rejecting those with $w$ that didn't match some other non-regular criterion. Given that our subset of $EPAL$ was formed by intersecting with a regular language, however, means that it must be context-free, implying that $1/2(X)$ is regular. – Patrick87 Oct 17 '14 at 22:01

Here is sdcvvc's answer in plain language. Suppose we are given a DFA for $L$ with set of states $S$, starting state $s_0$, accepting states $F$, and transition function $q$. We construct an NFA for $L_1$ as follows. The NFA maintains two states $(s_1,s_2) \in S^2$. Its initial states are $(s,s)$ for all $s \in S$, and its accepting states are $(s_0,f)$ for all $f \in F$. At state $(s_1,s_2)$, upon reading a symbol $a$, the NFA can move to any state $(t_1,t_2)$ such that $q(t_1,a) = s_1$ and $q(s_2,a) = t_2$. This completes the description of the NFA.
This NFA is trying to "prove" that $w^Rw$ is in $L$. The idea is that after reading a prefix $x$ of $y$, say $w = xy$ and so $w^Rw = y^Rx^Rxy$, the NFA will be in state $(q(s_0,y^R),q(s_0,y^Rx^Rx))$. At the beginning, that is when $x = \emptyset$, both states are the same $q(s_0,w^R)$, which the NFA guesses. This explains our initial states. Upon reading a character $a$ while at state $(s_1,s_2)$, the second part of the new state is $t_2 = q(s_2,a)$, while the first part is some $t_1$ satisfying $q(t_1,a) = s_1$. Finally, when we have finished reading the word, that is when $y = \emptyset$, we should be at the state $(s_0,q(s_0,w^Rw)) \in \{s_0\} \times F$, since $w^Rw \in L$. This explains our choice of accepting states.
Let $M$ be the syntactic monoid of $L$ and consider the monoid $M^{\operatorname{op}} \times M$ (where $M^{\operatorname{op}}$ is $M$ with multiplication flipped).
• I don't understand this answer. What of $M^{\mathrm{op}} \times M$? – Gilles Oct 17 '14 at 22:14
• It is the product of monoids $M^{\operatorname{op}}$ and $M$, with multiplication $(a,b)(c,d)=(ac,bd)$. – sdcvvc Oct 17 '14 at 22:18