# 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. Commented Apr 27, 2017 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. (see below.)

It is also possible to use closure properties. For each $$p,q\in Q$$, 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 initial $$p$$ and 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})$$.

nb. This formula is more or less equivalent to the most 'obvious' automaton construction, but hides the complexity of the states. Such an automaton works in three phases, each with appropriate states. (1) The first phase simulates $$\mathcal A$$ directly, but has no final states. At each state $$p$$ we may jump to the second phase, using an $$\varepsilon$$-transition. (2) We non-deterministically jump to some state $$q$$ in order to simulate a $$p$$ to $$q$$ computation in reverse. We store the pair $$(p,q)$$ in the states of the automaton for the second phase (or, equivalently, we construct $$Q\times Q$$-copies). The second phase follows the transitions in reverse. When at state $$p$$ we may jump to state $$q$$ for the third phase -the pair $$(p,q)$$ which is stored in the state at the beginning of the second phase. (3) The third phase is again a proper copy of $$\mathcal A$$, except we enter not necessarily at the initial state.

In total this construction will need some $$2+(Q\times Q)$$ copies of the original $$\mathcal A$$ and some rewiring of the transitions: $$\varepsilon$$-jumps between the phases, and inverted arrows for phase two.

• I have failed building an NFA even when trying to remember the choices made, as it just seemed like there are too many different branches and it became to hard for me to keep the information from jumbling up. The second approach did work for me though. Though I don't think I would have ever thought of iterating over pairs of states like that (my attempt was using the first and final letter of each section, but it failed as well). The idea here made it simple and was surprisingly easy to prove formally. Thank you! Commented Apr 27, 2017 at 22:59
• How would you build an NFA? Can you do it with two copies?$L$,$L^R$ and where we also define states p,q that “bound” y (then we will have a finite union which is regular) Commented Apr 26 at 14:56
• The union is over all $p,q\in Q$, so already is finite. My "nb" was meant to explain how this could be built into a FSA. The second phase needs to store the guess the end states $p,q$ of the reversed path, so that we can jump back from (2nd phase) $p$ to (3rd phase) $q$. For this I need to multiply by $Q\times Q$ cases, or states. Commented Apr 26 at 17:18
• I suggested a different solution. Not sure I understand what you mean.we can build an NFA with 3 copies (without p,q). But can we also build an NFA with 2 copies using p,q (to keep track of where y starts and ends) Commented Apr 26 at 18:05
• Yes. I believe we basically intend the same solution, but count differently. Not two copies, but three phases. However "storing" $p,q$ for the middle phase has to be done somewhere and this can be seen as $Q\times Q$-copies of the same automaton (one for each $p,q$). Then the two "forward" phases need to be distinguished, which necessitates another bit (or two copies rather than one). Commented Apr 26 at 18:34