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

Question

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*}

Answer 1

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