Prove que os idiomas regulares estão fechados no operador de ciclo

Eu tenho alguns dias em um exame e tenho problemas para resolver esta tarefa.

Seja uma linguagem regular sobre o alfabeto . Temos a operação E agora devemos mostrar esse também é regular.$L$$\Sigma$$\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$$\operatorname{cycle}(L)$

A referência é que poderíamos construir a partir de um DFA com a -NFA com e estados.$D=(Q,\Sigma,\delta, q_0, F)$$L(D) = L$$\epsilon$$N$$L(N) = \operatorname{cycle}(L)$$2 · |Q|^2 + 1$

A idéia é decidir não-deterministicamente no início quanto a palavra é alternada e ter uma cópia do autômato para cada caso. Em termos de autômato, isso significa que adivinhamos em que estado estaria depois de consumir o prefixo de uma palavra (que é um sufixo de nossa entrada) e começamos nesse estado.$D$

Agora a construção. Para cada estado , separe em duas partes e . contém os estados dos quais é alcançável e os estados que são alcançáveis ​​de :$q \in Q$$D$$A_1$$A_2$$A_1$$q$$A_2$$q$

^{[ fonte ]}

Observe que qualquer nó pode estar contido em e . Portanto, o número de estados pode dobrar se explicitarmos essa etapa.$A_1$$A_2$

Agora reconectamos esse autômato para que ele aceite todas as palavras para as quais marca o "ponto de ciclo":$q$

^{[ fonte ]}

Nós temosautômatos desta forma; crie um novo estado inicial que tenha -transitions para todos os seus estados iniciais. O autômato resultante aceita . No total, obtemos no máximo estados, apenassão possíveis mais estados do que as reivindicações de referência.$|Q|$$\varepsilon$$\operatorname{cycle}(L)$$|Q|\cdot(2|Q|+1) + 1$$|Q|$

Você pode alcançar estados modificando um pouco os autômatos do componente; elimine todas as substituindo as entrada por cópias de suas transições de saída. Ou seja, para cada par de transições , introduza uma transição .$2|Q|^2 + 1$$q_0$$\varepsilon$$(q_1,\varepsilon,q_0), (q_0,a,q_2)$$(q_1,a,q_2)$

Construção rigorosa e prova de correção permanecem como exercício.