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$.
It will be regular.


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