Problem bei der Implementierung des Brzozowski-Algorithmus

Ich habe versucht, den Brzozowski-Algorithmus zu implementieren, aber ich habe gerade festgestellt, dass er suboptimale Automaten für eine bestimmte Klasse von Eingaben erstellt und einen Status mehr hat, als im Ergebnis wirklich benötigt wird. Ich kann es auf einem trivialen Automaten zeigen:

   a b           a   b           a b            a     b            a b
>0 0 1  rev  *0 0,2  -   det  >0 - 1  rev  *0   -     -    det  >0 1 2
 1 1 2  -->   1  1   0   -->   1 2 5  -->   1   -    0,4   -->   1 1 2
*2 0 2       >2  -  1,2        2 2 3        2  1,2    -          2 2 3
                              *3 4 -        3   -     2         *3 1 3
                              *4 4 1        4  3,4    -          
                              *5 5 5        5   5    1,5         
                                           >6 3,4,5 1,2,5

Hier ist rev der Randumkehrteil , in dem ich bereits die Übergänge auf epsilon entfernt hatte, und det ist die Determinierung durch Powerset-Konstruktion, die rekursiv neue Zustände erzeugt, sobald sie entdeckt werden.

Das Problem hierbei ist folgendes: Wenn ich den zusätzlichen Zustand hinzufüge, um die drei verschiedenen Startzustände nach der ersten Kantenumkehr und der Powerset-Konstruktion auszugleichen, kehrt nichts mehr in diesen Zustand zurück, und daher kann ich ihn später nicht mehr entfernen, weil ich gleichwertig bin auf den ursprünglichen Startzustand.

Stimmt etwas nicht mit der Art und Weise, wie ich es mache? Vermisse ich etwas

algorithms automata finite-automata Přemysl J.
quelle

Antworten:

Das ist eine ausgezeichnete Frage!

Der Umkehrschritt in Brzozowskis Algorithmus führt keinen neuen virtuellen Startzustand ein, der über Übergänge zu den alten Akzeptanzzuständen führt . Stattdessen erlaubt es mehrere Startzustände, was kein großes Problem ist, wenn Sie den Produktautomaten ohnehin direkt nach der Umkehrung konstruieren. $\varepsilon$

Konzeptionell ist es am einfachsten, das Zurücksetzen und Bestimmen als einen einzigen Schritt zu betrachten. Wenn Ihre DEA , definieren Sie als die zurückgesetzte DEA wie folgt: $M=(Q,\Sigma,\delta,q_0,F)$ $M^R=(Q^R,\Sigma,\delta^R,q_0^R,F^R)$

$Q^R=\mathcal{P}(Q)$ ,
$q_0^R=F$ ,
$F^R=\{ P\subseteq Q \mid q_0\in P\}$ ,
$\delta^R(P,a):=\{ p\in Q \mid \delta(p,a)\in P\}$ .

(Möglicherweise möchten Sie Zustände ignorieren, die nicht erreichbar sind.)

Der Satz von Brzozowski besagt, dass eine minimale DEA ist, die akzeptiert . $(M^R)^R$ $L(M)$

Zur weiteren Lektüre schlage ich Elemente der Automatentheorie von Sakarovitch auf den Seiten 116-117 vor.

A.Schulz
quelle