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

Question

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.

Answer 1

Here is an idea which proves that $L_1$ is at least context free.

Suppose the (universal) alphabet for all languages is $A$. We know that the mirror language $L_R=\{w^Rw\mid w\in A^*\}$ is context free using a PDA. Now intersecting $L_R$ with your regular language $L$ we get $L_R\cap L$ which is definitely a context free language (general closure property). This then also proves that your language $L_1$ is at least context free as follows: Run a non-deterministic PDA which non-deterministically generates a random word $v$ (which in the end will turn out to be $w^R$) in the stack and in parallel runs the finite state automaton for $L$ on this word $v$. After this the PDA starts reading the actual input $w$. Symbol by symbol it compares this input against the symbols pulled from the stack (if there is any mismatch or if the stack is empty before $w$ is completely read, it stops and rejects) and also continues running the finite state automaton for $L$. Once the input is completely read the machine checks whether the stack is empty (i.e. $v$ matches $w^R$) and the finite state automaton for $L$ reached an accepting terminal state (i.e. $vw$ is in $L$). If both conditions are met the input word $w$ is accepted.

Now the harder question is whether your language $L_1$ can be in fact strictly context-free (i.e. non-regular). I have thought about a few examples but did not find any case where $L_1$ is non-regular, so maybe even the stronger result holds.

Answer 2

It is regular. Notice that $L^R=\{w^R\mid w\in L\}$ is also regular, and the idea here is to do a 'bidirectional check' by the NFA of $L$ and $L^R$, which are actually the same finite automata with all edges reversed.

To make it formal, suppose the NFA for $L$ is $\mathcal{A}=(\Sigma, Q, s, \delta_1, \{f\})$ (See this wiki page for model definition). Then we can construct a reversed automata $\mathcal{A}^R=(\Sigma, Q, f, \delta_2, \{s\})$ for $L^R$, where $$\delta_2(q,c)=\{q'\in Q\mid \delta_1(q',c)=q\}.$$ We assume that $\epsilon$-transitions are allowed, and to ensure the following constructions are reasonable, we assume that $q\in\delta_i(q,\epsilon)$ for all $q\in Q$, $i=1,2$.

We then define a direct product NFA $(\Sigma, Q\times Q, (s,f),\delta, F)$ such that $$\delta((q_1,q_2),c)=\delta_1(q_1,c)\times\delta(q_2,c),\ \forall c\in\Sigma\cup\{\epsilon\}$$ $$F=\{(q,q)\mid q\in Q\}$$ And it is clear that when a string $w$ is fed into this automata, what it does is to simulate $\mathcal{A}$ on $w$ from state $s$ and reversed $\mathcal{A}^R$ on $w$ from state $f$. If they meet at the same state after $w$ ends, we can concatenate their transitions to obtain a path from $s$ to $f$, in which the accepted string is exactly $ww^R$.

We conclude the above NFA accepts the language $L'=\{w\mid ww^R\in L\}$. Notice $$L_1=\{w^R\mid ww^R\in L\}=L'^R$$ and thus $L_1$ is also regular.