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

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.

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.$N$$M$$\lg_2N < M\leq N$$M$$S$$M$$S$

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$M$$\lg_2N < M\leq N$$M=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.$\frac{2^M !}{(2^M - N)!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).

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:

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.

$N$$S$$M$$\lg_2N<M\leq N$$y_{sft}$$y_{sft}$$f$ $t$ $s$$SM^2=32$ $y$$y_{0AA}, y_{1AA}$$y_{1AB}$$y_{1DA}$

$x_{dn}$$n$$d$$N=8$$M=4$$x$$k$$x_{kA}$$x_{kC}$$x_{kD}$$x_{kB}$ ist falsch.

$i < j$$\{A,B,\cdots, D\}$

$$(x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}).$$

$i$$j$$s$$k$$j$$l$$j$$l$$k$$o(SN^2)$

$$\begin{eqnarray*} x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\ x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\ & & \cdots \\ x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}. \end{eqnarray*}$$

$x_0A + x_0B + \cdots + x_0D$$f_n$$x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$$i$$\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$$j$

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.

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.