Beweis von Brzozowskis Algorithmus zur DFA-Minimierung?

Brzozowkis Algorithmus wird häufig zitiert. Einige Fragen geben hier Beispiele oder diskutieren ihre Komplexität. Aber ich konnte keinen Beweis für die Richtigkeit des Algorithmus finden. Wie beweisen wir es richtig? Jeder Beweis, der CS-Studenten zugänglich ist, wäre sehr willkommen.

Der Beweis für Brzozowskis Ergebnis ist technisch, aber nicht sehr kompliziert. Tatsächlich müssen wir nur eine Sequenz der Umkehrbestimmung berücksichtigen, um das gewünschte Minimalitätsergebnis zu erhalten. (Die erste Sequenz der Umkehrbestimmung führt zu einer deterministischen FSA für die Umkehrung der Originalsprache; der Minimalitätsnachweis gilt für die zweite Umkehrbestimmung.)

Zunächst muss man sich einen guten Überblick über die verschiedenen beteiligten Automaten verschaffen. Und Nerven aus Stahl.

Der Bau von Brzozowski. Sei ein deterministischer Automat für die Sprache . Wir nehmen an, dass alle Zustände von ab dem Anfangszustand erreichbar sind .$A = (Q, \Sigma, \delta, q_0, F)$$L=L(A)$$Q$$q_0$

Im ersten Schritt kehrt man den Automaten um: Alle Kanten werden invertiert und Anfangs- und Endzustand werden vertauscht. Informell erhalten wir den Automaten .$\mathrm{rev}(A) = (Q, \Sigma, \delta^{-1}, F, q_0)$

Im zweiten Schritt bestimmt man den so erhaltenen Automaten durch die Standardkonstruktion, behält aber nur erreichbare Zustände bei. Wir erhalten . Die Zustände von sind Mengen von Zuständen für : ; der Anfangszustand besteht aus den Anfangszuständen für , die Endzustände in : ; die Endzustände in sind die Zustände , die einen Endzustand für enthalten : iff .$A'= \mathrm{det}(\mathrm{rev}(A)) = (Q', \Sigma, \delta', q'_0, F')$$A'$$\mathrm{rev}(A)$$Q'\subseteq 2^Q$$\mathrm{rev}(A)$$Q$$q'_0 = F$$A'$$\mathrm{rev}(A)$$U\in F'$$q_0\in U$

Der Schlüssel des Beweises ist die folgende wichtige Beziehung zwischen den Automaten und .$A$$A'$

Grund Beobachtung: iff .$q\in \delta'(X,w^R)$$\delta(q,w) \in X$

Beweis (nur eine Seite). wenn in ein Zustand und ein Pfad von nach in mit der Bezeichnung . Das heißt aber, es gibt einen Pfad von nach mit der Bezeichnung in oder ; somit . Ende des Beweises.$q\in \delta'(X,w^R)$$p$$X$$p$$q$$\mathrm{rev}(A)$$w^R$$q$$p$$w$$A$$\delta(q,w) = p$$\delta(q,w) \in X$

Wie angekündigt, wird dies verwendet, um die wesentliche Eigenschaft zu beweisen, die wir benötigen.

Eigenschaft: ist minimal (und deterministisch für ).$A'$$L^R$

Beweis. Sei und zwei Zustände in , die nicht unterschieden werden können. Dies bedeutet, dass wir für jeden String wenn . Wir zeigen, dass jetzt und gleich sind.$U$$V$$A'$$w^R$$\delta'(U,w^R) \in F'$$\delta'(V,w^R) \in F'$$U$$V$

Durch die Konstruktion von wir die Ununterscheidbarkeit als iff .$F'$$\delta'(U,w^R) \ni q_0$$\delta'(V,w^R) \ni q_0$

Tragen Sie den Grund Beobachtung, und wir haben genau dann , wenn .$\delta(q_0,w) \in U$$\delta(q_0,w) \in V$

Aus dieser Gleichheit folgt , da angenommen wird, dass alle Zustände in erreichbar sind, so gibt es für jeden Zustand in oder eine Zeichenkette so dass . Ende des Beweises.$U=V$$Q$$p$$U$$V$$w$$p = \delta(q_0,w)$

Aber auch nach dem Beweis ist das Ergebnis immer noch echte Magie!