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?
For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?
formal languages;regular languages;closure properties
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})$.