Prouver que les langues régulières sont fermées sous l'opérateur de cycle

J'ai en quelques jours un examen et j'ai des problèmes pour résoudre cette tâche.

Laisser $L$ être une langue régulière sur l'alphabet $\Sigma$. Nous avons l'opération $\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$ Et maintenant, nous devons montrer que $\operatorname{cycle}(L)$ est également régulier.

La référence est que nous pourrions construire à partir d'un DFA $D=(Q,\Sigma,\delta, q_0, F)$ avec $L(D) = L$ une $\epsilon$-NFA $N$ avec $L(N) = \operatorname{cycle}(L)$ et $2 · |Q|^2 + 1$ États.

L'idée est de décider au début de façon non déterministe combien le mot est cyclé, et d'avoir une copie de l'automate pour chaque cas. En termes d'automate, cela signifie que nous devinons dans quel état$D$ aurait été après avoir consommé le préfixe d'un mot (qui est un suffixe de notre entrée), et commencer dans cet état.

Maintenant la construction. Pour chaque état$q \in Q$, séparé $D$ en deux parties $A_1$ et $A_2$. $A_1$ contient les états à partir desquels $q$ est accessible et $A_2$ les états accessibles depuis $q$:

^{[ source ]}

Notez que n'importe quel nœud donné peut être contenu dans les deux $A_1$ et $A_2$. Par conséquent, le nombre d'états peut doubler si nous rendons cette étape explicite.

Maintenant, nous recâblons cet automate pour qu'il accepte tous les mots pour lesquels $q$ marque le "point de cycle":

^{[ source ]}

On a $|Q|$automates de cette forme; créer un nouvel état initial qui a$\varepsilon$-transitions vers tous leurs états de départ. L'automate résultant accepte$\operatorname{cycle}(L)$. Au total, nous obtenons tout au plus$|Q|\cdot(2|Q|+1) + 1$ états, seulement $|Q|$ plus d'états que les revendications de référence sont possibles.

Vous pouvez réaliser $2|Q|^2 + 1$états en modifiant un peu les automates des composants; éliminer tout$q_0$ en remplaçant l'entrée $\varepsilon$-transitions avec copies de ses transitions sortantes. Autrement dit, pour chaque paire de transitions$(q_1,\varepsilon,q_0), (q_0,a,q_2)$, introduire une transition $(q_1,a,q_2)$.

Une construction rigoureuse et une preuve d'exactitude restent un exercice.