Algorithmus zum Verkleinern eines DFA durch Einführung von Nichtdeterminismus?

8

Dies hängt etwas mit einer anderen Frage zusammen, die ich gestellt habe , aber ich denke, es ist anders genug, um eine eigene Frage zu rechtfertigen.

Ich mache Forschungen, bei denen ich versuche, die Struktur von Komplementen einer bestimmten Klasse endlicher Sprachen zu finden. Es fällt mir leicht, die minimalen DFAs zu erhalten, die diese Sprachen akzeptieren, aber ich möchte untersuchen, welche Art von Struktur NFAs haben, die diese Sprachen akzeptieren, insbesondere wie Nichtdeterminismus bei der Zustandsgröße der Automaten hilft (die DFAs sind exponentiell groß).

Das Problem ist, dass die Haupt-NFA-Reduktionstechnik Äquivalenzen verwendet, die keine Reduktion erzeugen, wenn ich mit einem minimalen DFA beginne (da im Grunde dieselbe Technik verwendet wird). Wenn ich mit einem nicht minimalen DFA beginne, spuckt es nur den minimalen DFA aus.

Ich frage mich, ob es Algorithmen gibt, die mit einem DFA beginnen und ihn durch Einführung von Nichtdeterminismus auf einen kleineren NFA verkleinern können. Gibt es dafür "Standardtechniken"?

Ich habe Vorbestellungsreduzierungen gefunden , die vielversprechend, aber schwer umzusetzen sind. Ich bin offen für viele Vorschläge.

jmite
quelle
Es ist möglich, aber Pspace vollständig, um eine minimale NFA für einen DFA zu finden
vzn
Ja, aber es gibt Reduktionstechniken, die nützlich sind, aber nicht in allen Fällen das Minimum finden. Ich bin mehr daran interessiert, wie Nichtdeterminismus die Zustandsgröße reduziert, als den Minimalfall tatsächlich zu finden.
Jmite

Antworten:

4

Für eine effiziente Heuristik würde ich vorschlagen, in der CAD-Literatur zum Problem der Zustandscodierung nachzuschauen (Zuweisen von binären Bezeichnern zu Zuständen eines DFA, um den logischen Aufwand für die Zustandsübergangsfunktion zu minimieren). Devadas und Newton, "Zerlegung und Faktorisierung der sequentiellen Endlichkeit State Machines, IEEE TCAD , 8 (11): 1206-1217, 1989, weist darauf hin, dass es eine enge Beziehung zwischen der Zustandscodierung und der Zerlegung der Zustandsmaschine gibt.

Wenn Sie für einen DFA mit Zuständen jedem Zustand eine eindeutige M- Bit-Zustandskennung zuweisen ( lg 2 N < M N ), haben Sie den DFA im Wesentlichen in ein Netzwerk von M interagierenden Zwei-Zustands-Maschinen zerlegt . Entsprechend: Sie haben eine Menge S mit M Elementen definiert und jedem Zustand in Ihrem ursprünglichen DFA eine eindeutige Teilmenge von S zugewiesen . Dies ist auch das, was der Rabin-Scott-Powerset-Konstruktionsalgorithmus tut. Durch eine Zustandscodierung auf dem DFA versuchen wir also, die Menge, von der der Powerset-Konstruktionsalgorithmus ausgegangen ist, zurückzuentwickeln.NMlg2N<MNMSMS

Beim herkömmlichen Problem der Zustandscodierung sind alle Codierungen zulässig, und es gibt eine objektive Funktion (in Bezug auf den Logikaufwand in der Zustandsübergangsfunktion), die Sie minimieren möchten. Um eine NFA zu generieren, müssen Sie eine eingeschränkte Version des folgenden Problems lösen, wobei:

Eine Codierung von Bitkennungen in die DFA-Zustände stellt eine NFA dar, wenn für jedes Symbol im Alphabet die Übergangsfunktion für jedes Bit eine einfache Disjunktion von Bits ist. (Keine Konjunktion oder Negation ist erlaubt.)M

Sie können also alle Bit-Codierungen für alle lg 2 N < M N auflisten und prüfen, ob jede die Bedingung erfüllt. (Beachten Sie, dass für M = N die triviale "One-Hot" -Codierung immer die Einschränkungen erfüllt und Ihnen den DFA gibt.) Die Aufzählung ist jedoch lächerlich groß (Di Michelis Lehrbuch gibt sie als etwa 2 M an !Mlg2N<MNM=N.) Der Grund, warum ich die CAD-Literatur vorschlage, ist, dass es Techniken gibt, mit denen diese Suche implizit durchgeführt werden kann, anstatt sie aufzuzählen (z. B. mithilfe von BDDs, sieheLin, Touati und Newton, "Es ist mir egal, die Minimierung von mehrstufigen Sequenzen zu minimieren." Logic Networks,Int'l Conf Comp-Aided DsgnICCAD-90: 414-417, 1990.2M!(2MN)!M!

Beispiel

Nehmen Sie den folgenden DFA (mit einer Statuscodierung, die ich durch Betrug abgeleitet habe (ich habe den DFA aus einer NFA mit Rabin-Scott generiert, und die Codierung repräsentiert die von Rabin-Scott ausgewählten Teilmengen).

DFA von Rabin-Scott

Wenn wir die Bits in der Zustandszuweisung ABCD aufrufen, ist die Übergangsfunktion A = A, B = A, C = B, D = C, wenn das Eingangssymbol 1 ist. Wenn das Eingabesymbol 0 ist, ist die Übergangsfunktion A = A, C = B, D = C. Dies ist eine rein disjunktive Übergangsfunktion ohne Konjunktion oder Negation, daher gibt uns diese Zustandscodierung eine NFA. Die Zustände in der NFA entsprechen eins zu eins den Bits in der Codierung, und die Übergangsfunktion ist wie folgt:

NFA für Rabin-Scott

Formulierung als boolesches Erfüllbarkeitsproblem

Die obige informelle Beschreibung führt direkt zu einer Codierung als boolesches Erfüllbarkeitsproblem. Es gibt eine Reihe von Variablen, die die Übergänge in der NFA beschreiben, und eine Reihe von Variablen für die DFA-Statuscodierung, die von Rabin-Scott für die ausgewählte NFA abgeleitet würden. Die Übergänge des spezifischen DFA, den Sie zerlegen möchten, werden verwendet, um Einschränkungen für die NFA-Übergänge festzulegen.

NSMlg2N<MNysftysftf t sSM2=32 yy0AA,y1AAy1ABy1DA

xdnndN=8M=4xkxkAxkCxkDxkB ist falsch.

i<j{A,B,,D}

(xiAxjA)+(xiBxjB)++(xiDxjD).

ijskjljlko(SN2)

xjA=ysAAxiA+ysBAxiB++ysDAxiDxjB=ysABxiA+ysBBxiB++ysDBxiDxjD=ysADxiA+ysBDxiB++ysDDxiD.

x0A+x0B++x0DfnxiAfA+xiBfB++xiDfDi¬(xjAfA+xjBfB++xjDfD)j

Wanderlogik
quelle
Diese Idee des Reverse Engineering der Teilmengenkonstruktion ist genau das, wonach ich suche. Es scheint kompliziert zu sein, also werde ich mir etwas Zeit nehmen, um es zu analysieren. Vielen Dank!
jmite
1
Ich habe versucht herauszufinden, wie ich es als SAT-Problem umformulieren kann, habe aber noch nicht genug Zeit dafür aufgewendet.
Wandering Logic
3

Das Minimieren von NFAs ist schwierig, so schwierig, dass selbst die Annäherung schwierig ist. siehe Minimierung von NFAs und regulären Ausdrücken von Gramlich und Schnitger (2005). Dieser Artikel scheint auch einige nützliche Referenzen zu haben, z. B. NFA-Reduktionsalgorithmen mittels regelmäßiger Ungleichungen von Champarnaud und Coulon (2002), die Minimierungstechniken enthalten.

Raphael
quelle
Ja, ich bin okay, wenn es nur eine Reduzierung und keine vollständige Minimierung ist. Ich werde einen Blick darauf werfen, diese Referenzen sehen aber wirklich gut aus.
jmite
2

Es gibt einige Vorstellungen von kanonisch FSAs , die nicht unbedingt deterministisch sind, daher kann kleiner sein als die minimale DFA. Ein Beispiel sind die "Residual" -FSAs, für die man kanonische Residual-FSAs ganz direkt berechnen kann, siehe F. Denis, A. Lemay und A. Terlutte. "Residual Finite State Automata", Fundamenta Informaticae 51 (4): 339-368, 2002 . Es gibt mehrere Alternativen.

phs
quelle
Können Sie das Rechnen ganz direkt erklären? Auf diese Weise ist die Berechnung des kanonischen Rest-FSA ein PSPACE-vollständiges Problem. Das könnte für mich immer noch funktionieren (meine Maschinen sind ziemlich klein), aber ich bin vorsichtig.
jmite
Insbesondere bin ich verwirrt darüber, wie ich feststellen würde, ob ein Zustand in einer Maschine "abdeckbar" ist, wie auf Seite 17 des Papiers definiert, kurz vor Abschnitt 5 Lemma 4.
jmite