Show that moving one symbol to the end still makes a regular language

Question

Question

For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following

For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^*$), $\texttt{MOVE}(\sigma)=wa$

This is equivalent to moving the starting symbol to the end. For example, $\texttt{MOVE}(10110)=01101$.

Show that for a regular language $L$, the language $\texttt{MOVE}(L) = \{\texttt{MOVE}(\sigma): \sigma \in L\}$ is also regular.

My Attempt

After reading this post, I know I could prove a language $L$ is regular by showing that $L$ could be expressed as a DFA, NFA, or regular expression.

I tried different (vaguely related) directions

• I have proved that: if $L$ is regular, then its reverse $L^R$ is also regular. However, in terms of $\texttt{MOVE}(L)$, only one symbol is reversed while the order of others is preserved.
• $\texttt{MOVE}(L)$ seems to be related to converting between left and right quotients. But I do not how to proceed as quotients are defined upon two languages rather than one.

$$ L_1/L_2 = \{w\vert \exists x: x\in L_2 \wedge wx \in L_1\}\\ L_1\backslash L_2 = \{w\vert \exists x: x\in L_2 \wedge xw \in L_1\} $$

Except these attempts, I do not know how to approach this problem. It would be great if anyone provide some pointer for me.

Answer 1

Consider a DFA for the original language with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct an NFA for the new language which operates roughly as follows:

• It first guesses the initial symbol $a$.
• It then reads the word $w$.
• A state is accepting if $wa \in L$.

To implement this, the set of states will be $\Sigma \times Q$, that is, the set of pairs $(a,q)$ where $a \in \Sigma$ and $q \in Q$. The initial states are $(a,\delta(q_0,a))$. A state $(a,q)$ is final if $\delta(q,a) \in F$. Finally, the transition relation is $\delta((a,q),b) = (a,(q,b))$.

---

You can solve this in many other ways. One of the simplest is using closure properties. Let $a^{-1}L = \{w \in \Sigma^* : aw \in L\}$, which is a quotient $L \setminus \{a\}$ per your definition. Then $$ \texttt{MOVE}(L) = \sum_{a \in \Sigma} (a^{-1}L)a. $$ You can even implement this using regular expression. Given a regular expression for $L$, construct a regular expression for $a^{-1}L$ using the following rules:

• $a^{-1} \emptyset = a^{-1} \epsilon = \emptyset$.
• $a^{-1}a = \epsilon$ and $a^{-1}b = \emptyset$, where $b \neq a$ is a symbol.
• $a^{-1}(r_1+r_2) = a^{-1}r_1+a^{-2}r_2$.
• If $r_1$ doesn't generate $\epsilon$ then $a^{-1}(r_1r_2) = (a^{-1}r_1)r_2$.
• If $r_1$ does generate $\epsilon$ then $a^{-1}(r_1r_2) = (a^{-1}r_1)r_2 + a^{-1}r_2$.
• $a^{-1}(r^*) = (a^{-1}r)r^*$.

You can determine whether $r$ generates $\epsilon$ recursively. Denoting this predicate by $E$,

• $E(\emptyset) = E(a) = F$, $E(\epsilon) = T$.
• $E(r_1+r_2) = E(r_1) \lor E(r_2)$.
• $E(r_1r_2) = E(r_1) \land E(r_2)$.
• $E(r^*) = T$.

This gives a mechanical procedure to compute a regular expression $a^{-1}r$ satisfying $L[a^{-1}r] = a^{-1}L[r]$. We can then define $$ \texttt{MOVE}(r) = \sum_{a \in \Sigma} (a^{-1}r)a, $$ which satisfies $L[\texttt{MOVE}(r)] = \texttt{MOVE}(L[r])$.