Beweisen Sie, dass reguläre Sprachen unter dem Zyklusoperator geschlossen sind

Ich habe in ein paar Tagen eine Prüfung und habe Probleme, diese Aufgabe zu lösen.

Sei eine reguläre Sprache über dem Alphabet Σ . Wir haben den Betrieb Zyklus ( L ) = { x y | x , y ∈ & Sgr; *  und  y x ∈ L } Und nun sollten wir das zeigen Zyklus ( L ) ist auch regelmäßig.$L$$\Sigma$$\operatorname{cycle}(L) = \{ xy \mid x,y\in \Sigma^* \text{ and } yx\in L\}$$\operatorname{cycle}(L)$

Die Referenz ist, dass wir aus einem DFA mit L ( D ) = L a ϵ -NFA N mit L ( N ) = Zyklus ( L ) und 2 · konstruieren könnten | Q | 2 + 1 Zustände.$D=(Q,\Sigma,\delta, q_0, F)$$L(D) = L$$\epsilon$$N$$L(N) = \operatorname{cycle}(L)$$2 · |Q|^2 + 1$

Die Idee ist, zu Beginn nicht deterministisch zu entscheiden, wie viel das Wort getaktet wird, und für jeden Fall eine Kopie des Automaten zu haben. In Bezug auf den Automaten bedeutet dies, dass wir erraten, in welchem ​​Zustand sich nach dem Konsumieren des Präfixes eines Wortes (das ein Suffix unserer Eingabe ist) befunden hätten, und in diesem Zustand beginnen.$D$

Nun zum Bau. Trennen Sie D für jeden Zustand in zwei Teile A 1 und A 2 . A 1 enthält die Zustände, von denen aus q erreichbar ist, und A 2 die Zustände, von denen aus q erreichbar ist :$q \in Q$$D$$A_1$$A_2$$A_1$$q$$A_2$$q$

^{[ Quelle ]}

$A_1$$A_2$

$q$

^{[ Quelle ]}

$|Q|$$\varepsilon$$\operatorname{cycle}(L)$$|Q|\cdot(2|Q|+1) + 1$$|Q|$

$2|Q|^2 + 1$$q_0$$\varepsilon$$(q_1,\varepsilon,q_0), (q_0,a,q_2)$$(q_1,a,q_2)$

Strenge Konstruktion und Korrektheitsnachweis bleiben als Übung.