We have automat $A$ for language $L$. Construct automat for $Cycle(L)$ where $Cycle(L)=\{uv:vu\in L\}$.

I have a problem with this exercise. Help me, please.


$A = (Q_A, \Sigma, \delta, q_0, F_A)$- automat for language $L$
$A'$ - copy of automat $A$ such that there is no accept state and every state is beginning state. For each state $ (q,q')\in Q_{A'} $ we create copy of $A$ $(A_{q})$ such that only accepting state is $q$. $A'=(Q_{A'},\Sigma, \delta', Q_{A'}, \emptyset)$
$Q_{A'}=Q\times Q $
$\delta'((q_1, q_2), a\in \Sigma)=(\delta(q_1, a), q_1) $
$\delta'((q_1, q_2), \epsilon)= q_0 \in A_{q_2} \text{ where $q_1$$\in$ $F_A$ }$

  • $\begingroup$ See this question. $\endgroup$ – J.-E. Pin Apr 8 '15 at 6:46
  • $\begingroup$ I edited my post (it is my idea - I didn't look to your hint). Look again please and check it :) $\endgroup$ – user220688 Apr 8 '15 at 15:45
  • $\begingroup$ I am not sure to understand your construction. Since $A'$ has no accepting state, it accepts the empty language. $\endgroup$ – J.-E. Pin Apr 8 '15 at 15:54
  • $\begingroup$ $A'$ has no acc state - it isn't problem. We have ϵ-transition - we jump from $A'$ (we started in $(q_2,q_2)$ and go to any state (correponding to accepting state in $A$). into new automat $A_{q_2}$ where we have exactly one acc state $\endgroup$ – user220688 Apr 8 '15 at 17:31

Your Answer

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

Browse other questions tagged or ask your own question.