NFA-zu-DFA-Frage

Question

Erstens geht es hierbei nicht um die Frage, ob der Algorithmus einen NFA in einen DFA umwandeln soll.

Es ist bekannt (und bewiesen), dass der äquivalente DFA eines NFA höchstens 2 hat^N Staaten, auch wenn es in den meisten Fällen mehr oder weniger so viele Staaten wie die NFA gibt.

Wie kann ich eine Schätzung für die Anzahl der Staaten vorhersagen, die das NFA-äquivalente DFA haben wird?Für welche Art von NFA muss ein gleichwertiger DFA 2 haben?^N Zustände?

Ich stelle diese Frage, um einige NFAs „erfinden“ zu können, die ohne Rücksicht auf Minimierung mit Sicherheit 2 hervorbringen^N - 1 Zustände plus der „tote Zustand“.

Answer 1

Die Anzahl der Zustände explodiert aufgrund Nichtdeterminismus, was der Schlüssel zu Ihrer Frage ist.

Wenn Sie eine NFA nehmen, bei der jeder Übergang einzigartig bestimmt ist, dh eine deterministische NFA, dann ist es nichts anderes als ein normales DFA. Sobald Sie jedoch einen Zustand haben, in dem zwei Übergänge möglich sind, unterscheidet er sich vom DFA.

Betrachten Sie den Conversion -Algorithmus und prüfen Sie, was passiert, wenn Sie zwei oder mehr Übergänge mit demselben Etikett für einen Zustand haben. Hier benötigen Sie diese neuen Staaten, die den Staatensätzen entsprechen.

Die Frage kommt also darauf, herauszufinden, wie viele dieser Superset -Staaten tatsächlich erreichbar sind. Natürlich könnten Sie dafür einen ausgefallenen Algorithmus erfinden, aber um die richtige Zahl zu erhalten, führen Sie einfach den normalen Konvertierungsalgorithmus aus und entfernen Sie unerreichbare Zustände.

Was eine NFA mit N-Zuständen betrifft, für die die äquivalente DFA 2^N-Staaten darüber nachdenken, den Nichtdeterminismus auszunutzen. Die erste Idee wäre, alle Übergänge gleich zu kennzeichnen, aber das funktioniert nicht so gut. Denken Sie stattdessen daran, dass Sie in der Lage sein müssen, alle Teilmengen von Staaten mit jeweils einem Etikett zu erreichen.

Wenn Sie den Startzustand nicht zählen, können Sie die folgende Konstruktion durchführen: Erstellen von N -Knoten und für jeden von 2^N ein eindeutiges Etikett erstellen und in der NFA einen Übergang mit diesem Etikett zu jedem Knoten dieses Satzes hinzufügen. Dies gibt Ihnen eine NFA mit n +1 -Zuständen (1 ist der Startzustand), in dem die DFA 2^n +1 Zustände benötigt. Natürlich wird es schwieriger, wenn Sie nach der Minimierung 2^n DFA -Zustände haben möchten.

Answer 2

Ok, beginnen Sie mit der Annahme, dass n -> n.Nun multiplizieren Sie für jeden nichtdeterministischen Übergang, bei dem Sie von einem Zustand in x andere Zustände gelangen können, Ihre Schätzung mit x.Dies ist möglicherweise nicht genau, da Sie möglicherweise doppelt zählen.Aber es sollte Ihnen eine Obergrenze geben.

Der einzig sichere Weg besteht jedoch darin, ein entsprechendes DFA zu erstellen und dann die Staaten zu zählen (glaube ich).

Schließlich können Sie wahrscheinlich einige der DFAs (und auch NFAs) vereinfachen, aber das ist eine ganz neue Geschichte ...

Answer 3

Nehmen Sie als Funktion von N mit Startzustand und endgültigem Zustand n, dieser NFA A(N):

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

Es sollte offensichtlich sein, dass dies alle Saiten in akzeptiert [ab]* dessen n-te-from-Last-Brief ist a.

Die Bestimmung von A(N) muss sich effektiv an die vorherigen N-1-Buchstaben erinnern (Sie müssen alle Positionen in diesem Fenster kennen, die waren a, so dass Sie sagen können, ob es eine gab, wenn die Saite unerwartet endet, ob es eine gab a N Briefe).

Ich bin mir nicht sicher, ob dies genau die Anzahl der von Ihnen gewünschten Zustände trifft, aber es liegt zumindest innerhalb eines Faktors von 2 - allen Teilmengen von {0,...,N} sind möglich, aber Sie sind auch immer in S. Das sollte sein 2^(N+1) Staaten, aber A(N) hatte N+2 Zustände.

Answer 4

Um die hervorragende Antwort von Jonathan Graehl weiter zu erweitern.

Zu jedem Zustand hinzufügen 0, 1, ..., N von A(N) eine Selbstschließung beschriftet c, dh, Sie fügen die folgenden Übergänge hinzu:
0 c-> 0
1 c-> 1
...
N c-> N

Dann angenommen c Feuer niemals, die DFA enthält das gleiche 2^(N+1) Staaten von Jonathans DFA. Allerdings wann immer c wird aus einem Zustand beobachtet {S,j,k,...,z} <> {S} Wir erreichen den Zustand {j,k,...,z}. Daher alle Untergruppen von {S,0,...,N} sind möglich, außer dem leeren Satz und der DFA hat 2^(N+2)-1 Staaten während A(N) hat N+2 Zustände.