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.

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