9
$\begingroup$

I've got in a few days an exam and have problems to solve this task.

Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation $\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$ And now we should show that $\operatorname{cycle}(L)$ is also regular.

The reference is that we could construct out of a DFA $D=(Q,\Sigma,\delta, q_0, F)$ with $L(D) = L$ a $\epsilon$-NFA $N$ with $L(N) = \operatorname{cycle}(L)$ and $2 · |Q|^2 + 1$ states.

$\endgroup$
1

1 Answer 1

17
$\begingroup$

The idea is to decide nondeterministically at the beginning how much the word is cycled, and have a copy of the automaton for every case. In terms of the automaton, that means that we guess in which state $D$ would have been after consuming a word's prefix (which is a suffix of our input), and start in that state.

Now the construction. For every state $q \in Q$, separate $D$ into two parts $A_1$ and $A_2$. $A_1$ contains the states from which $q$ is reachable and $A_2$ the states that are reachable from $q$:

enter image description here
[source]

Note that any given node may be contained in both $A_1$ and $A_2$. Therefore, the number of states can double if we make this step explicit.

Now we rewire this automaton so it accepts all words for which $q$ marks the "cycle point":

enter image description here
[source]

We get $|Q|$ automata of this form; create a new initial state which has $\varepsilon$-transitions to all their starting states. The resulting automaton accepts $\operatorname{cycle}(L)$. Altogether, we get at most $|Q|\cdot(2|Q|+1) + 1$ states, only $|Q|$ more states than the reference claims are possible.

You can achieve $2|Q|^2 + 1$ states by modifying the component automata a little bit; eliminate all $q_0$ by replacing the incoming $\varepsilon$-transitions with copies of its outgoing transitions. That is, for every pair of transitions $(q_1,\varepsilon,q_0), (q_0,a,q_2)$, introduce a transition $(q_1,a,q_2)$.

Rigorous construction and correctness proof remain as exercise.

$\endgroup$
2
  • $\begingroup$ but how you can prove this you just contructed a nfa ? $\endgroup$ May 23, 2012 at 16:27
  • 3
    $\begingroup$ @SadGolduhren Raphael constructed an NFA (it's finite because there's a finite bound on the number of states). To see that this NFA recognizes the same language as the original, observe the paths through the automata: $q_0 \to q$ and $q \to q_F$ (where $q_F$ is any final state reached from $q$) become $q \to q_F$ and $q_0 \to q'$, and $q_F \stackrel\epsilon\to q_0$ completes the path. $\endgroup$ May 23, 2012 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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