# Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular

Does the following work and is there anything possibly simpler?

Let $$X = (Q, \Sigma, \delta, s, F)$$ be a DFA for $$A$$. Intuitively, we want to "remember" (or guess) two states $$p$$ and $$q$$ such that $$s \stackrel{z}{\longrightarrow^{\ast}} p \stackrel{y}{\longrightarrow^{\ast}} q \stackrel{x}{\longrightarrow^{\ast}} f$$ where $$f \in F$$ is a valid "run" in $$X$$ (Also by $$\stackrel{w}{\longrightarrow^\ast}$$ I mean a transition over letters of $$w$$).

Consider $$X' = \left( Q \times Q \times \left\{ 0, 1, 2 \right\}, \Sigma \cup \{\varepsilon\}, \delta', S, F' \right)$$ where $$S = \left\{ (p, q, 0) \mid \text{q is reachable from p} \right\}$$ and $$F' = \left\{ (p, p, 2) \mid p \in Q \right\}$$. The idea will be to break the automaton into 3 parts joined together by $$\varepsilon$$-transitions. The transition function is defined as follows: \begin{align*} \delta'\left( (p, q, n), a \right) &= (p, \delta(q, a), n) \quad\forall\, n \in \left\{ 0, 1, 2 \right\}, \\ \delta'\left( (p, f, 0), \varepsilon \right) &= (p, p, 1)\quad\text{where f \in F}, \\ \delta'\left( (p, q, 1), \varepsilon \right) &= (p, s, 2). \end{align*} As is evident, we want to store the state $$p$$ in a memory'' throughout any run starting at $$(p, q, 0)$$. This way, if $$s \stackrel{z}{\longrightarrow^{\ast}} p \stackrel{y}{\longrightarrow^{\ast}} q \stackrel{x}{\longrightarrow^{\ast}} f$$ is a valid run in $$X$$, then we have the following valid run in $$X'$$ and vice versa: $$\begin{equation*} (p, q, 0) \stackrel{x}{\longrightarrow^{\ast}} (p, f, 0) \stackrel{\varepsilon}{\longrightarrow} (p, p, 1) \stackrel{y}{\longrightarrow^{\ast}} (p, q, 1) \stackrel{\varepsilon}{\longrightarrow} (p, s, 2) \stackrel{z}{\longrightarrow^{\ast}} (p, p, 2). \end{equation*}$$

• If you can prove that it works, then it works. Nov 9, 2021 at 7:36
• Thanks @YuvalFilmus, it does seem there is a flaw where I wrote "vice versa": a valid run in $X'$ won't necessarily give a valid run in $X$. I feel storing $q$ in addition to $p$ might be the way to go. Nov 9, 2021 at 8:17

You can basically follow the same reasoning without explicitly constructing the resulting finite automaton, using closure properties instead. That might save a lot of technical details. And it makes states $$p,q$$ explicit, rather than remembering them in states.
Given $$X=(Q,Σ,δ,s,F)$$ the DFA for $$A$$, now consider some derived automata that only change initial and final states. Let $$X_{pq}=(Q,Σ,δ,p,\{q\})$$ and $$X_{pF}=(Q,Σ,δ,p,F)$$.
Then $$L(X) = \bigcup_{p,q\in Q} L(X_{sp}){\cdot}L(X_{pq}){\cdot}L(X_{qF})$$.
The language you are looking for equals $$\bigcup_{p,q\in Q} L(X_{qF}){\cdot}L(X_{pq}){\cdot}L(X_{sp})$$.