Algorithmen zur Minimierung von Moore-Automaten

Brzozowskis Algorithmus kann auf Moore-Automaten erweitert werden, aber seine zeitliche Komplexität ist im Allgemeinen exponentiell. Gibt es einen anderen Algorithmus zur Minimierung von Moore-Automaten? Was sind die Laufzeiten dieser Algorithmen, falls vorhanden?

Der ursprüngliche DFA-Minimierungsalgorithmus wurde tatsächlich für Moore-Maschinen entwickelt , die sich an ihrem anscheinend besser beobachtbaren Verhalten orientieren. Der hier vorgestellte Algorithmus ist jedoch eine Rekonstruktion aus der DFA-Minimierung, da ich die historischen Beweise nachträglich entdeckt habe.

Nach Wikipedia (mit einigen Änderungen in der Notation):

Eine Moore-Maschine kann als 6-Tupel das aus Folgendem besteht:$(Q, q_0, \Sigma, \Pi, \delta, \gamma)$

• eine endliche Menge von Zuständen$Q$
• ein Startzustand (auch Anfangszustand genannt) der ein Element von$q_0$$Q$
• eine endliche Menge, die als Eingabealphabet$\Sigma$
• eine endliche Menge namens Ausgabealphabet$\Lambda$
• eine Übergangsfunktion die einen Zustand und das Eingabealphabet dem nächsten Zustand zuordnet $\delta : Q \times \Sigma \rightarrow Q$
• eine Ausgabefunktion die jeden Zustand dem Ausgabealphabet zuordnet $\gamma : Q \rightarrow \Pi$

Nach dieser Definition ist eine Moore-Maschine ein deterministischer Finite-State-Wandler.

Ich habe keine Referenz für die Minimierung von Moore-Automaten. Es scheint jedoch nicht allzu schwer, sich einen Algorithmus vorzustellen, der von dem Algorithmus abgeleitet ist, der für deterministische Finite-State-Automaten verwendet wird.

Die Idee der DFA-Minimierung basiert auf der Myhill-Nerode-Charakterisierung regulärer Sprachen .

Definieren Sie bei einer gegebenen Sprache und einem Paar von Zeichenfolgen und eine Unterscheidungserweiterung als Zeichenfolge , sodass genau eine der beiden Zeichenfolgen und zu . Definieren Sie eine Beziehung für Zeichenfolgen nach der Regel, dass wenn es keine unterscheidende Erweiterung für und . Es ist leicht zu zeigen, dass eine Äquivalenzbeziehung für Zeichenfolgen ist und somit die Menge aller Zeichenfolgen in Äquivalenzklassen unterteilt.x y z x z y z L R L x R L y x y R $L$$x$$y$$z$$xz$$yz$$L$$R_L$$x R_L y$$x$$y$$R_L$

Das Myhill-Nerode-Theorem besagt, dass genau dann regulär ist, wenn R L eine endliche Anzahl von Äquivalenzklassen hat, und dass außerdem die Anzahl von Zuständen im kleinsten deterministischen endlichen Automaten (DFA), der L erkennt, gleich der Anzahl von Äquivalenzklassen ist in R L .$L$$R_L$$L$$R_L$

In der Tat ist jeder Zustand des kleinsten DFA so, dass W q, wie oben definiert, eine der Äquivalenzklassen für die Beziehung R L ist .$q$$W_q$$R_L$

Für einen nicht minimalen DFA für die reguläre Sprache ist es leicht zu zeigen, dass jede Menge W q Zeichenfolgen enthält, die alle zu derselben äquivalenten Klasse in Bezug auf R L gehören .$L$$W_q$$R_L$

Daher besteht die Minimierung des DFA tatsächlich aus dem Zusammenführen von Zuständen (als Sätze äquivalenter Zeichenfolgen betrachtet), wenn gezeigt wird, dass zwei unterschiedliche Zustände äquivalente Zeichenfolgen enthalten.

Zu diesem Zweck existieren zwei relativ schnelle Algorithmen, der Moore-Algorithmus (1956), der in der Zeit und der Hopcroft-Algorithmus (1971), der in der Zeit O ( n log n ) liegt .$O(n^2)$$O(n\log n)$

Die Erweiterung auf Moore-Automaten lässt sich am besten verstehen, wenn die Äquivalenzbeziehung als für einen Wandler T neu definiert wird . Die Beziehung R L befasste sich mit der Frage, ob zukünftige Eingaben gleichwertig zu einem akzeptierenden Zustand führen würden. Die R T ¨Aquivalenzrelation von Moore - Automaten betreffen , ob zukünftiger Eingang die gleiche Leistung erzeugen wird.$R_T$$T$$R_L$$R_T$

Daher definieren wir bei gegebenem Wandler und zwei Strings x und y eine unterscheidende Erweiterung als einen String z, so dass T ( x z ) = T ( x ) u und T ( y z ) = T ( y ) v mit u ≠ v , dh so, dass das Ausgangsverhalten des Wandlers für z unterschiedlich ist, je nachdem, ob er x oder y folgt .$T$$x$$y$$z$$T(xz)=T(x)u$$T(yz)=T(y)v$$u\neq v$$z$$x$$y$

Wiederum eine Äquivalenzrelation, alle Strings in Dividieren Σ * in Äquivalenzklassen. Im Fall einer Moore-Maschine entsprechen diese Klassen wieder dem Zustand des Minimalwandlers.$R_T$$\Sigma^*$

Der folgende Algorithmus ahmt den Moore-Algorithmus zur DFA-Minimierung nach.

Wir definieren eine anfängliche Partition von Q in Klassen von Zuständen S e wie folgt:$\mathcal P$$Q$$S_e$

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Dann teilen wir die Klassen in wie folgt auf:$\mathcal P$

Wiederholen Sie nacheinander für jede Klasse von Zuständen , bis sich nichts mehr ändert. Wiederholen Sie ∀ a ∈ Σ $S$
$\ \ $ $\forall a\in\Sigma,\;$
$\ \ \ \ $ Wenn dannnichtsanderestun, S in Teilmengen S i aufteilen,so dass esfür jede Teilmenge S i eine andere Klasse S ' ∈ P gibt, so dass ∀ q ∈ S i$\exists S'\in \mathcal P,\; \forall q\in S,\; \delta(q,a)\in S'$
$\ \ \ \ $ $S$$S_i$
$\ \ \ \ \ \ $$S_i$$S'\in \mathcal P$ (die Teilmengen S i ersetzen S in P )$\forall q\in S_i,\; \delta(q,a)\in S'$
$\ \ \ \ \ \ $$S_i$$S$$\mathcal P$

Wenn keine Klasse mehr vorhanden ist, die aufgeteilt werden muss, bilden die verbleibenden Zustandsklassen die Zustände der minimalen Moore-Maschine.

Konstruktionsbedingt haben alle Zustände in einer Klasse dieselbe Ausgabe, die die Ausgabe für die Klasse ist.

In ähnliche Weise für jede Eingabe gehen, alle Zustände in einer Klasse zu einem gewissen Zustand in der gleichen anderen Klasse, die die Übergangsfunktion für die minimalen Moore - Automaten definiert.$a\in\Sigma$

$n=|Q|$$s=|\Sigma|$
$n$$O(sn^2)$

Ich habe keine Referenz für diese Minimierung von Moore-Maschinen. Möglicherweise ist es in seiner Arbeit enthalten:

Moore, Edward F. (1956). "Gedankenexperimente an sequentiellen Maschinen". Automata Studies , Annals of Mathematical Studies (Princeton, New Jersey: Princeton University Press) (34): 129-153.

Dieses Papier ist die Hauptreferenz zur Einführung von Moore Machines . Es ist auch die Referenz für den DFA-Minimierungsalgorithmus von Moore . Es sollte daher überraschend sein, wenn die Anpassung des Algorithmus an die Minimierung von Moore-Maschinen in diesem Artikel nicht zumindest vorgeschlagen wurde. Ich habe das Papier überprüft, und die vorgestellte Version des Minimierungsalgorithmus gilt eigentlich für Moore-Maschinen, nicht für DFA. Das Papier ist gut geschrieben, aber der Stil der Zeit macht es etwas schwieriger zu lesen. Es ist interessant zu sehen, dass viele der Ideen der Myhill-Nerode-Theorie der Finite-State-Maschinen bereits in diesem Artikel skizziert sind.

$O(sn\log n)$

Eine Version von Brzozowskis Algorithmus unter Verwendung von Ableitungen regulärer Ausdrücke ist in [2], Kapitel 12, Abschnitt 4, angegeben, wo er [4] gutgeschrieben wird. Siehe [1] und [3] für den allgemeineren Fall von nachfolgenden Wandlern (die Terminologie ist etwas veraltet und der Begriff sequentieller Wandler ist heutzutage wahrscheinlich angemessener).

[1] C. Choffrut, Minimierung von Teilwandlern: eine Übersicht, Theoret. Comp. Sci. 292 (2003), 131–143.

[2] S. Eilenberg, Automata, Languages ​​and Machines, vol. A, Academic Press, 1974.

[3] J.-E. Pin, Ein Tutorial zu sequentiellen Funktionen . (Folien)

[4] GN Raney, Sequential Functions, JACM 5 (1958), 177–180.

Der Brzozowski-Algorithmus ist ein schlechter Ausgangspunkt (wenn Sie sich mit asymptotischer Worst-Case-Laufzeit befassen). Sogar Wikipedia sagt Ihnen so viel:

Wie Brzozowski (1963) feststellte, erzeugt das Umkehren der Kanten eines DFA einen nicht deterministischen endlichen Automaten (NFA) für die Umkehrung der Originalsprache und das Konvertieren dieses NFA in einen DFA unter Verwendung der Standard-Powerset-Konstruktion (Konstruktion nur der erreichbaren Zustände von Der konvertierte DFA) führt zu einem minimalen DFA für dieselbe umgekehrte Sprache. Wenn Sie diese Umkehroperation ein zweites Mal wiederholen, wird ein minimaler DFA für die Originalsprache erzeugt. Die Worst-Case-Komplexität von Brzozowskis Algorithmus ist exponentiell, da es reguläre Sprachen gibt, für die der minimale DFA der Umkehrung exponentiell größer ist als der minimale DFA der Sprache, [6] aber häufig besser abschneidet, als dieser Worst-Case vermuten lässt.

Der Algorithmus hat sogar auf DFA eine exponentielle Worst-Case-Laufzeit , da er einen Automaten für die Umkehrung berechnet, der möglicherweise exponentiell groß sein muss. Ihr Problem kommt also nicht von der Erweiterung auf Wandler.

Versuchen Sie, einen anderen DFA-Minimierungsalgorithmus anzupassen.