Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Exercise 5.4, due May 24th. – Raphael May 30 '12 at 8:32
up vote 14 down vote accepted

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

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

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.

share|cite|improve this answer
but how you can prove this you just contructed a nfa ? – Sad Golduhren May 23 '12 at 16:27
@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. – Gilles May 23 '12 at 18:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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