2
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.