Wir wissen, dass DFAs in ihrer Ausdruckskraft NFAs entsprechen; Es gibt auch einen bekannten Algorithmus zum Konvertieren von NFAs in DFAs (leider kenne ich jetzt den Erfinder dieses Algorithmus), der im schlimmsten Fall Zustände liefert , wenn unser NFA Zustände hat. S
Meine Frage ist: Was bestimmt das Worst-Case-Szenario?
Hier ist eine Transkription eines Algorithmus im Falle von Mehrdeutigkeiten:
Sei eine NFA. Wir konstruieren einen DFA wobeiA ' = ( Q ' , Σ , δ ' , q ' 0 , F ' )
- ,
- ,
- und
- ,
Wobei die erweiterte Übergangsfunktion von .
Antworten:
Der Algorithmus, auf den Sie sich beziehen, heißt Powerset Construction und wurde erstmals 1959 von Michael Rabin und Dana Scott veröffentlicht.
Um Ihre Frage wie im Titel angegeben zu beantworten, gibt es keinen maximalen DFA für eine reguläre Sprache, da Sie immer einen DFA nehmen und so viele Zustände hinzufügen können, wie Sie möchten, mit Übergängen zwischen ihnen, aber ohne Übergänge zwischen einem der ursprünglichen Zustände und einer der neuen. Somit sind die neuen Zustände ab dem Anfangszustand nicht erreichbar , so dass sich die vom Automaten akzeptierte Sprache nicht ändert (da für alle gleich bleibt ). .δ ( q 0 , w ) w ∈ & Sigma; *q0 δ^(q0,w) w∈Σ∗
Das heißt, es ist klar, dass es keine Bedingungen für eine NFA geben kann, dass ihre äquivalente DFA maximal ist, da es keine eindeutige äquivalente DFA gibt. Im Gegensatz dazu ist der minimale DFA bis zum Isomorphismus einzigartig.
Ein kanonisches Beispiel einer Sprache, die von einem NFA mit Zuständen mit äquivalentem DFA von Zuständen akzeptiert wird , ist Ein NFA für ist mit , und für . Der DFA, der sich aus der Anwendung der Powerset-Konstruktion auf diesen NFA ergibt, hat Zustände, da Sie alle Wörter der Länge2 n L = { w ∈ { 0 , 1 } ∗ : | w | ≥ n und das n- te Symbol vom letzten ist 1 } . L A = ⟨ Q , { 0 , 1 } , δ , q 0 , { q n + 1 } ⟩ δ ( q 0 , 0 )n+1 2n
quelle
Der schlechteste Fall von ergibt sich aus der Anzahl der Teilmengen von Zuständen der NFA. Damit der Algorithmus aus Kleenes Theorem einen äquivalenten DFA mit der ungünstigsten Anzahl von Zuständen liefert, muss es eine Möglichkeit geben, zu jeder möglichen Teilmenge von Zuständen in der NFA zu gelangen. Ein Beispiel mit zwei Zuständen über dem Alphabet hat einen Übergang vom Anfangszustand zum einzigen Akzeptanzzustand bei Symbol , einen Übergang vom Akzeptanzzustand zurück zum Anfangszustand bei und einen Übergang vom Akzeptanzzustand zurück zu sich selbst entweder auf einem oder a . Die Saiten , , und2s { a , b } ein b ein b λ ein b a b führen zu Teilmengen , { q 2 } , { } und { q 1 , q 2 } , und diese würden separate Zustände in der DFA benötigen, die Kleene gibt.{ q1} { q2} { } { q1, q2}
quelle
Ich glaube, dies ist eine Frage an der Grenze des Wissens, dh im Grunde genommen eine Forschungsfrage. Nach einer schnellen Google-Suche scheint es größtenteils offen zu sein. Außerdem habe ich jahrelang geglaubt, dass es wichtig und mit den unteren Grenzen der Komplexitätstheorie verbunden ist. Sie erwähnen eine statistische Analyse nicht direkt, aber das ist es, was Ihre Frage impliziert. Hier sind zwei Beispiele für statistische Studien zu DFAs / NFAs, die ähnlich sind, um den allgemeinen Ansatz für Fragen dieser Art zu zeigen. Die empirische Grundlagenforschung zu solchen Fragen ist offenbar noch weitgehend unerforscht. Zwar bezieht sich die zweite Frage nicht direkt auf Ihre Frage, aber es ist die aktuellste, die ich finden konnte.
Diese Metrik würde sich auf graphentheoretische Metriken wie Kantendichte usw. beziehen. Es gibt wahrscheinlich einige sehr wichtige Metriken der Graphentheorie oder eine Mischung von Metriken, die das "Aufblasen" schätzen, aber es ist für mich nicht sofort offensichtlich. Ich könnte vielleicht so etwas wie grafische Farbmetriken oder Clique-Metriken vorschlagen. Testen Sie dann die Metrik anhand der beiden Sätze "Aufblasen" und "Nicht aufgeblasen".
Andere Antworten auf Ihre Frage geben bisher nur einen Beispielfall für eine "Explosion" (nützlich für eine Fallstudie), gehen jedoch nicht auf das Hauptproblem einer allgemeinen Metrik ein.
Ein weiterer Bereich, in dem ein erfolgreich entwickeltes empirisches Forschungsprogramm untersucht werden muss, ist die SAT-Übergangspunktforschung. Das hat sehr tiefe Verbindungen zu physikalischen und thermodynamischen Konzepten entwickelt. Es scheint mir wahrscheinlich, dass ähnliche Konzepte hier anwendbar sind. Beispielsweise ist es wahrscheinlich, dass man analoge Metriken für Übergangspunkttypen findet; wahrscheinlich Kantendichte usw. Man beachte die Parallelen zur Kolmogorov-Kompressibilitätstheorie.
Ich vermute auch, dass NFAs, die "explodieren", im Vergleich zu solchen, die nicht ganz analog zu "harten" oder "einfachen" Fällen von NP-vollständigen Problemen sind.
Eine weitere Möglichkeit, dieses Problem zu untersuchen, wäre die Formulierung eines NFA-Minimierungsproblems. Das heißt, wenn ein DFA vorliegt, finde ich, dass der minimale NFA, den ich zuletzt gehört habe (vor vielen Jahren), immer noch ein offenes Problem war.
[1] Zur Leistung von Automatenminimierungsalgorithmen Marco Almeida, Nelma Moreira, Rogério Reis
[2] Automaten erkennen keine Worte: Ein statistischer Ansatz Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu
quelle