Verallgemeinerung von Brzozowskis DFA-Minimierungsalgorithmus auf endliche Automaten mit verschiedenen Klassen von Akzeptanzzuständen?

9

Brzozowskis Algorithmus zum Umwandeln eines DFA in einen äquivalenten DFA mit minimalem Zustand ist bemerkenswert einfach: Wenn die NFA bezeichnet, die durch Umkehren aller Kanten in einem DFA wird, wird der alte Startzustand zu einem akzeptierenden Zustand und der alte akzeptierende Zustand Zustände beginnen Zustände, und wenn die Teilmenge Aufbau des NFA des Anwendens die Folge bezeichnet , dann ist ein Minimum-state DFA mit derselben Sprache wie .R(D)DP(N)N

P(R(P(R(D))))
D

Wir können uns einen DFA als ein Rechengerät vorstellen, das eine Eingabezeichenfolge akzeptiert und dann 0 ausgibt, wenn in einem zurückweisenden Zustand endet, und 1, wenn in einem akzeptierenden Zustand endet. Eine natürliche Verallgemeinerung von DFAs assoziierte jeden Zustand im DFA mit einer natürlichen Zahl zwischen 0 und einschließlich .wwwk−1

Nach meinem besten Wissen ist es möglich, diese modifizierten Klassen von DFAs mithilfe eines auf Unterscheidbarkeit basierenden Minimierungsalgorithmus wie dem kanonischen von Hopcroft zu minimieren. Ich kann jedoch nicht sehen, wie es möglich wäre, Brzozowskis Minimierungsalgorithmus an diese neue Klasse von Automaten anzupassen, da der Schlüsselschritt (Umkehren des Automaten) in dieser verallgemeinerten Einstellung keine klare Interpretation mehr hat.

Gibt es eine bekannte Verallgemeinerung des Brzozowski-Algorithmus zur Minimierung dieser Art von Automaten? Wenn nicht, gibt es theoretische Gründe, warum wir erwarten würden, dass ein derart modifizierter Algorithmus nicht existieren würde?

automata-theory minimization templatetypedef
quelle
Die "Verallgemeinerung" scheint nicht klar definiert zu sein. was ist ? geht es nur darum, jeden Zustand in einem DFA einem begrenzten ganzzahligen Wert zuzuordnen? dann was? Was ist ein Beispiel? Wer arbeitet damit? etck
vzn
@vzn Sie können sich vorstellen, dass jeder Status in einem normalen DFA entweder mit 0 oder 1 verknüpft ist (Status ablehnen bzw. akzeptieren). Ich denke darüber nach, dies auf den Fall zu verallgemeinern, in dem jedem DFA-Status ein Wert in ist und der DFA die dem Status zugeordnete Nummer ausgibt dass die Zeichenfolge endet in.{0,1,2,3,...,k−1}
templatetypedef
ok, das wird in der Post überhaupt nicht kommuniziert. "Der DFA gibt das # aus, das dem Status zugeordnet ist, in dem die Zeichenfolge endet." Außerdem haben DFAs technisch gesehen keine "Ausgabe". Vielleicht meinst du FSM-Wandler? Es gibt tatsächlich eine partielle Theorie im Zusammenhang mit der Minimierung von FSM-Wandlern , die anscheinend ("noch"?) nicht vollständig mit der DFA-Minimierung verbunden ist.
vzn

Antworten:

7

Die Antwort auf Ihre Frage lautet ja.

Siehe Bonchi, Bonsangue, Rutten und Silvas Artikel Brzozowskis Algorithmus (co) algebraisch (kürzere Konferenzversion) und Algebra-Coalgebra-Dualität in Brzozowskis Minimierungsalgorithmus (längere Journalversion mit mehr Verallgemeinerungen).

Sie geben eine (leicht) kategorische Darstellung des Brzowzowski-Algorithmus und leiten daraus Versionen für allgemeinere Klassen von Automaten ab, einschließlich Moore-Automaten (die eine positive Antwort auf Ihre Frage geben).

Neel Krishnaswami
quelle
6

Um Neels Antwort zu ergänzen, diskutieren wir in meinem Buch Automatic Sequences with Jean-Paul Allouche DFAOs (deterministische endliche Automaten mit Ausgaben), nach denen Sie genau gefragt haben (ordnen Sie jedem Zustand eine Ausgabe zu). Und Satz 4.3.3 beschreibt, wie man eine solche Maschine umkehrt.

Jeffrey Shallit
quelle