$L' = \{x\#y $ | $xy \in L, yx \notin L\} $ where $L$ is regular, Prove $L'$ is regular.

Question

$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!

Answer 1

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.

Answer 2

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