$L' = \{x\#y $ | $xy \in L, yx \notin L\} $ where $L$ is regular, Prove $L'$ is regular. $L' = \{x\#y $ | $xy \in L, yx \notin L\} $ where $L$ is regular
Hey I need some help with proving that $L'$ is regular by construction and/or regular closures.
Just to make clear $\#$ is a specific char indicates $\#$.
$x$ and $y$ are in $\Sigma^*$. $xy\in L$ ($x$ concatenated with $y$).
Thanks!
 A: Consider a NDFSA $M = (Q, \Sigma, \Delta, q_0, F)$ for $L$. Note that we are not permitting $\epsilon$-transitions for simplicity.
Define $Q' = \{0, 1\} \times Q$. Define $q_0' = (0, q_0)$. Define $F' = \{1\} \times F$.
Define
$\Delta'((0, q), s) = \begin{cases} 
  \{0\} \times \Delta(q, s) & s \neq \# \\
  \{0\} \times \Delta(q, s) \cup \{(1, q)\} & s = \#
\end{cases}$
$\Delta'((1, q), s) = \{1\} \times \Delta(q, s)$
Then I claim $M' = (Q', \Sigma, \Delta', q_0', F')$ is a NDFSA for $L'$.
For suppose we have $xy \in L$. Then it is easy to show that our automaton will accept $x \# y$. Let $n$ be the length of $x$, and let $m$ be the length of $y$. Then consider an accepting run $q_0, ..., q_n, ..., q_{n + m}$ for $xy$ in $M$. Then we see that the run $(0, q_0), ..., (0, q_n), (1, q_n), ..., (1, q_{n + m})$ will be an accepting run for $x \# y$ in $M'$.
Conversely, consider an accepting run $q'_0, ..., q'_k$ of a string $s$ in the NDFSA $M'$. Since $q'_k \in F'$, we know that $q'_k$ is of the form $(1, q)$. Then we can conclude that $q'_k = (1, q) \neq (0, q_0) = q'_0$ and hence $k \neq 0$. Then there must be some $n$ such that $p_1(q'_n) = 0$ and $p_1(q'_{n + 1}) = 1$. And in fact, there is a unique such $n$. Then we can write $s = x \# y$, where $x$ is the first $n$ characters and $y$ is the last $k - n - 1$ characters of $s$. And from the definition of $\Delta'$, we see that $p_2(q'_0), ..., p_2(q'_n), p_2(q'_{n + 2}), ..., p_2(q'_k)$ will be an accepting run of $xy$ in $M$.
Since $M'$ is a NDFSA which accepts $L'$, we see that $L'$ is a regular language.
Note: $p_1((a, b)) = a$ and $p_2((a, b)) = b$.
A: Let ${\cal A} = (Q,A,\cdot,i,F)$ be the minimal deterministic complete automaton of $L$. For each state $p, q$ of $\cal A$, let $L_{p,q}$ be the language accepted by $\cal A$ with $p$ as initial state and $q$ as unique final state. Then
$$
L' = \Bigl( \bigcup_{q \in Q, f \in F} L_{i,q}\#L_{q,f}\Bigr) \cap \Bigl( \bigcup_{q \in Q, f \in Q-F} L_{q,f}\#L_{i,q}\Bigr)
$$
Thus $L'$ is regular.
