Prove that regular languages are closed under the cycle operator

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,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.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1986