Probar que los idiomas regulares están cerrados bajo el operador de ciclo

Tengo en unos días un examen y tengo problemas para resolver esta tarea.

Dejar $L$ ser un lenguaje regular sobre el alfabeto $\Sigma$. Tenemos la operacion $\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$ Y ahora deberíamos demostrar que $\operatorname{cycle}(L)$ También es regular.

La referencia es que podríamos construir a partir de un DFA $D=(Q,\Sigma,\delta, q_0, F)$ con $L(D) = L$ una $\epsilon$-NFA $N$ con $L(N) = \operatorname{cycle}(L)$ y $2 · |Q|^2 + 1$ estados.

La idea es decidir de manera no determinista al principio cuánto se cicla la palabra, y tener una copia del autómata para cada caso. En términos del autómata, eso significa que adivinamos en qué estado$D$ habría sido después de consumir el prefijo de una palabra (que es un sufijo de nuestra entrada), y comenzar en ese estado.

Ahora la construcción. Para cada estado$q \in Q$separado $D$ en dos partes $A_1$ y $A_2$. $A_1$ contiene los estados desde los cuales $q$ es accesible y $A_2$ los estados a los que se puede llegar desde $q$:

^{[ fuente ]}

Tenga en cuenta que cualquier nodo dado puede estar contenido en ambos $A_1$ y $A_2$. Por lo tanto, el número de estados puede duplicarse si hacemos explícito este paso.

Ahora volvemos a cablear este autómata para que acepte todas las palabras para las cuales $q$ marca el "punto de ciclo":

^{[ fuente ]}

Obtenemos $|Q|$autómatas de esta forma; crear un nuevo estado inicial que tiene$\varepsilon$-transiciones a todos sus estados iniciales. El autómata resultante acepta$\operatorname{cycle}(L)$. En total, llegamos a lo más$|Q|\cdot(2|Q|+1) + 1$ estados, solo $|Q|$ más estados que las reclamaciones de referencia son posibles.

Puedes lograr $2|Q|^2 + 1$estados modificando un poco el autómata componente; eliminar todo$q_0$ reemplazando el entrante $\varepsilon$-transiciones con copias de sus transiciones salientes. Es decir, para cada par de transiciones.$(q_1,\varepsilon,q_0), (q_0,a,q_2)$, introduce una transición $(q_1,a,q_2)$.

La construcción rigurosa y la prueba de corrección permanecen como ejercicio.