Wie kann man beweisen, dass DFAs von NFAs eine exponentielle Anzahl von Zuständen haben können?

20

Alle nicht deterministischen endlichen Automaten können in äquivalente deterministische endliche Automaten umgewandelt werden. Bei deterministischen endlichen Automaten ist jedoch nur ein Pfeil pro Symbol zulässig, der auf einen Zustand verweist. Daher sollten seine Staaten Mitglieder der Machtgruppe der Staaten der NFA sein. Dies scheint darauf hinzudeuten, dass die Anzahl der Zustände des DFA in Bezug auf die Anzahl der Zustände des NFA exponentiell skalieren könnte. Ich fragte mich jedoch, wie ich das tatsächlich beweisen könnte.

John Hoffman
quelle
7
Es ist eine vernünftige Frage, und der Aufbau ist nicht ganz offensichtlich, aber es könnte immer noch eine Hausaufgabe sein. Es wäre also hilfreich zu erfahren, warum Sie es wissen möchten.
Es gibt hier einige Konstruktionen , aber es scheint, als müsste es irgendwo in einer Zeitung stehen. Ich weiß nicht von einem ref. Ich denke auch, dass es eine Konstruktion gibt, bei der die NFA in ihren aktiven Zuständen binär zählt und erst nach etwa Übergängen akzeptiert ...? 2n
VZN

Antworten:

15

Eine Operation, die eine NFA in eine andere NFA umwandelt, dies jedoch nicht für eine DFA tut, ist die Umkehrung (alle Pfeile in die entgegengesetzte Richtung zeigen und Anfangszustände durch akzeptierende Zustände tauschen). Die Sprache, die vom transformierten Automaten erkannt wird, ist die umgekehrte Sprache .LR={un1u0u0un1L}

Eine Idee ist es daher, nach einer Sprache zu suchen, die asymmetrisch aufgebaut ist. Zukünftig sollte diese Sprache durch Überprüfen der ersten Symbole erkannt werden , wobei nur -Zustände erforderlich sind . In umgekehrter Richtung sollte es notwendig sein, die letzten Zustände zu speichern , wofür Zustände erforderlich sind , wobei die Alphabetgröße ist.n + O ( 1 ) n A n + O ( 1 ) Ann+O(1)nAn+O(1)A

Wir suchen nach einer Sprache der Form wobei aus Wörtern der Länge , eine nichttriviale Teilmenge des Alphabets ist und keine weitere Einschränkung bietet. Wir könnten genauso gut das einfachste Alphabet (ein Singleton-Alphabet reicht nicht, kleinere NFAs gibt es nicht) und . Ein nichttriviales bedeutet . Was , so verlangen wir, dass es nicht mit korreliert (damit der DFA für die umgekehrte Sprache das Gedächtnis von behalten muss ): takeM n n S M ' A = { a , b } M ' = A * S S = { a } M n S S M n = A nMnSMMnnSMA={a,b}M=ASS={a}MnSSMn=An .

Also sei . Es wird von einem einfachen DFA mit Zuständen erkannt . n + 2Ln=(a|b)na(a|b)n+2

dfa

Das Umkehren ergibt eine NFA, die erkennt .LnR=(a|b)a(a|b)n

nfa

Der minimale DFA , der erkennt, hat mindestens Zustände. Dies liegt daran, dass alle Wörter der Länge im DFA unterschiedliche Zustände erreichen müssen. (Mit anderen Worten, sie gehören zu verschiedenen Myhill-Nerode-Äquivalenzklassen .) Um dies zu beweisen, nehmen Sie zwei verschiedene Wörter und lassen eine Position sein, an der sie sich unterscheiden. ( ). wir ohne der Allgemeinheit an, und . Dann ist und ( ist eine unterscheidende Erweiterung für 2 n + 1LnR2n+1 u , v A n + 1 k u kv k u k = ein v k = b u b kL R n v b kL R n B k u v u v L R n u b k v b k2n+1u,vAn+1kukvkuk=avk=bubkLnRvbkLnRbku und ). Wenn und in einem DFA, der erkennt, zu demselben Zustand führen würden, würde dies und , was unmöglich ist, da einer zu einem akzeptierenden Zustand führt und der andere nicht.vuvLnRubkvbk

Danksagung: Dieses Beispiel wurde in Wikipedia ohne Erklärung zitiert . Der Artikel verweist auf einen Artikel, den ich nicht gelesen habe und der eine engere Grenze enthält:
Leiss, Ernst (1981), "Prägnante Darstellung regulärer Sprachen durch boolesche Automaten", Theoretical Computer Science 13 (3): 323–330, doi: 10.1016 / S0304-3975 (81) 80005-9 .

Gilles 'SO - hör auf böse zu sein'
quelle
Logische Antwort: Zustände in DFA werden als Speicher verwendet (um einige Informationen wie den Ein- / Ausschalter des Lüfters zu speichern), sodass das, was in einem einzelnen Zustand in DFA dargestellt werden kann, unter Verwendung einer Kombination von Zuständen in äquivalentem NFA dargestellt werden kann. Dies ist der Grund, warum NFA im Vergleich zu äquivalenten DFA weniger Zustände aufweist. Nun , wenn Sie Zustände in einem Satz dann eingestellt alle möglichen Kombinationen von sind Power-Set , das ist , also wenn wir einen NFA von Reverse Zuständen in äquivalente DFA, dann wird DFA höchstens besteht aus seinem Staaten. - Macht das Sinn? Q Q 2 n n 2 nnQQ2nn2n
Grijesh Chauhan
1
@GrijeshChauhan Dies ist nicht das, was die Frage gestellt hat. Ja, es ist leicht zu erkennen, dass es für jeden NFA mit Zuständen einen DFA mit höchstens Zuständen gibt. Aber hier wollen wir sehen, dass die Schranke erreicht ist, dh, dass es für jedes eine NFA mit Zuständen gibt, so dass die kleinste äquivalente DFA mindestens Zustände hat (oder nahe daran, hier beweise ich die Schranke ). 2 n n n 2 n 2 n - 1n2nnn 2n2n1
Gilles 'SO- hör auf böse zu sein'
hmm ... nachdem ich deine antwort zweimal gelesen habe und aus kommentar "aber hier wollen wir sehen, dass die grenze erreicht ist" hätte ich jetzt verstehen können. Vielen Dank.
Grijesh Chauhan
8

Betrachten Sie die folgende Sprachfamilie: Ln={x1,x2,,xk#xk+1:i{1,,k} with xi=xk+1}

Das Alphabet von ist . { # , 1 , , n }Ln{#,1,,n}

Es gibt eine NFA mit -Zuständen, die die Sprache erkennt . Es hat Kopien. In der ten Kopie erraten wir, dass der letzte Buchstabe , und überprüfen unsere Vermutung. Es ist einfach, eine solche Kopie mit Zuständen zu erstellen. Der einzige Nichtdeterminismus ist im Anfangszustand.L n n i i 3O(n)Lnnii3

Es gibt jedoch keinen DFA, der mit weniger als Zuständen erkennt , da sich ein DFA intuitiv Teilmengen von merken muss .2 O ( n ) { 1 , , n }Ln2O(n){1,,n}

Ich bin mir ziemlich sicher, dass Sipsers Buch dieses Beispiel hat.

Kerl
quelle
Die Konstruktion in Sipers Buch erzeugt einen DFA mit genau 2 ^ n Zuständen. Wenn die NFA den Status Q hat, ist der Status der DFA Pow (Q), um alle möglichen 'parallelen' Status zu simulieren, in denen sich eine NFA-Mächtigkeit befindet Die in einem Standardtext dafür verwendete Konstruktion zeigt deutlich die Möglichkeit von Zuständen mit exponentiellen Zahlen, es scheint mir, dass dies kein Forschungsniveau ist. Könnte jedoch als Referenzanfrage geeignet sein.
Logan Mayfield
8

Ein weiteres Beispiel ist die Sprache aller Wörter, bei denen ein Symbol des Alphabets fehlt. Wenn das Alphabet die Größe , kann ein NFA einen Anfangszustand "erraten" und so die Sprache mit Zuständen akzeptieren . Andererseits ist bei Verwendung des Nerode-Theorems leicht zu erkennen, dass die Größe des minimalen DFA für diese Sprache beträgt .n 2 nnn2n

Dieses Beispiel zeigt auch, dass NFAs unter Komplementation eine exponentielle Explosion erleiden können. In der Tat ist bekannt, dass jede NFA (oder sogar kontextfreie Grammatik) für die Sprache aller Wörter, die alle Symbole des Alphabets enthalten, eine exponentielle Anzahl von Zuständen aufweisen muss.

Yuval Filmus
quelle
1
Falls jemand außer mir es falsch interpretiert hat, bedeutet "Wörter, denen ein Symbol des Alphabets " . (Nicht: Wörter, die jeden Buchstaben außer einem enthalten, oder Wörter, in denen die Buchstaben in der angegebenen Reihenfolge aufgelistet sind, und überspringen einen.)σΣ(Σσ)
6005
Es ist ein merkwürdiges Beispiel, da die Größe von für die Beispielfamilie nicht konstant gehalten wird. Wenn wir ein festes binäres Alphabet annehmen, können wir das Beispiel anpassen, indem wir die Buchstaben binär codieren , aber das Ergebnis ist etwas anders. Angenommen, ich habe keinen Fehler gemacht, dann können wir eine NFA der Größe und die DFA muss mindestens groß sein . n O ( n 2 ) 2 n 2 nΣnO(n2)2n2n
6005
Der Punkt dieses Beispiels ist, dass das Aufblasen genau der Konstruktion des Leistungssatzes entspricht. Es gibt ein binäres Beispiel mit der gleichen Vergrößerung, aber es ist komplizierter.
Yuval Filmus
Ja, es ist ein schönes Beispiel.
6005
1
O(nlogn)