# For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

[Where $w^R$ is the reverse of $w$]

My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language. Any hints?

• Non-determinism is a good idea; combine that with how the automaton for $L^R$ works. – Raphael Apr 27 '17 at 18:11

Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$. It is possible to construct a new finite automaton for the new language $L'=\{xy^Rz\mid xyz\in L\}$. You need nondeterminism and extra components in the states to remember the choices made.
It is also possible to use closure properties. Let $\mathcal A_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A_{p.F}$ for final states $F$.
Now $L'= \bigcup_{p,q} L(\mathcal A_{q_0,p})\cdot L(\mathcal A_{p,q})^R\cdot L(\mathcal A_{q,F})$.