Problem Detail: 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,yin Sigma^* text{ and } yxin 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.
Asked By : user1594
Answered By : Raphael
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$: 
[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”:
[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.
[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”:
[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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1986
