Warum heißt NFA nicht deterministisch?

14

Ich habe diese [irgendwie witzige] Frage im Kopf. Warum ist das nicht-deterministischen endlichen Automaten genannt nicht-deterministisch, während wir die Übergänge für Eingänge definieren. Nun, obwohl es mehrere und Epsilon- Übergänge gibt, sind diese definiert, was bedeutet, dass die Maschine für diese Übergänge deterministisch ist. Das heißt, es ist deterministisch.

finite-automata nondeterminism Madhusoodan P
quelle

12

Nichtdeterministisch, wie es in der theoretischen Informatik verwendet wird, unterscheidet sich von zufällig.

AdrianN

10

Es ist die Wahl zwischen den Übergängen, die nicht deterministisch ist.

Reinierpost

Was ist eine NFA? (Für die Unaufgeklärten unter uns)

DarcyThomas

@DarcyThomas, die erste Einführung, die ich hatte, war swtch.com/~rsc/regexp/regexp1.html . Es ist eine gute Lektüre - es ist nicht der Zweck des Artikels, NFAs vorzustellen, aber es leistet gute Arbeit bei der Diskussion regulärer Ausdrücke.

Wildcard

1

@Trilarion cs.stackexchange.com/questions/5008/…

adrianN

22

"Deterministisch" bedeutet "Wenn Sie das System zweimal in dieselbe Situation versetzen, wird garantiert, dass Sie beide Male dieselbe Wahl treffen".

"Nicht deterministisch" bedeutet "nicht deterministisch", oder mit anderen Worten "wenn Sie das System zweimal in dieselbe Situation versetzen, trifft es möglicherweise beide Male dieselbe Wahl oder nicht".

Ein nicht deterministischer endlicher Automat (NFA) kann mehrere Übergänge aus einem Zustand heraus haben. Dies bedeutet, dass es mehrere Möglichkeiten gibt, was in dieser Situation getan werden kann. Es ist nicht gezwungen, immer dasselbe zu wählen; Bei einem Eingang wird möglicherweise der erste Übergang und bei einem anderen Eingang derselbe Übergang ausgewählt.

Hier können Sie sich "Situation" als "Zustand der NFA zusammen mit dem Symbol vorstellen, das als nächstes von der Eingabe gelesen wird". Selbst wenn beide identisch sind, kann ein NFA immer noch mehrere übereinstimmende Übergänge haben, die aus diesem Zustand entfernt werden können, und es kann willkürlich auswählen, welcher davon verwendet werden soll. Im Gegensatz dazu verfügt ein DFA nur über einen passenden Übergang, der in dieser Situation ausgeführt werden kann. Daher hat er keine Wahl - er folgt immer demselben Übergang, wenn er sich in dieser Situation befindet.

DW
quelle

"Es kann beliebig wählen, welchen man nehmen soll." Also hat es im Grunde einen probabilistischen Charakter?

Trilarion

@Trilarion, nein, es kommt darauf an, ob es zum Akzeptieren des Zustands führt. In der Tat ist probabilistische FA eine Verallgemeinerung für NFA.

Rus9384

"Nicht deterministisch" bedeutet "nicht deterministisch", oder mit anderen Worten "wenn Sie das System zweimal in dieselbe Situation versetzen, trifft es möglicherweise beide Male dieselbe Wahl oder nicht". Damit meinen Sie, dass die Maschine dieselbe Zeichenfolge in zwei verschiedenen Fällen akzeptieren und ablehnen kann.

Madhusoodan P

3

@MadhusoodanP Ihre Intuition ist korrekt, was hier geschrieben wurde, und das führt uns zu dem, was in dieser Antwort fehlt: Bei der Analyse von NFAs berücksichtigen wir immer alle möglichen Ausführungspfade. Solange ein Pfad in dieser Maschine zu einem akzeptierenden Zustand führt, betrachten wir die Eingabe als akzeptiert. Es geht also überhaupt nicht um die Wahrscheinlichkeit, sondern nur darum, ob ein akzeptierender Zustand erreicht werden kann oder nicht. Diese Intuition wird klarer, wenn wir darüber nachdenken, wie NFAs zu DFAs reduziert werden: Wir müssen alle möglichen Ausführungen des NFA simulieren, was zu einer exponentiellen Explosion in der Konstruktion führt.

ComicSansMS

3

Eine Möglichkeit zur Visualisierung besteht in der Annahme, dass die NFA bei Auswahl mehrerer Übergänge alle Übergänge ausführt . Sie erstellen eine baumartige Struktur aller Zustände, die von einer Eingabezeichenfolge erreicht werden. Wenn einer der Zweige mit einem Akzeptanzstatus endet, wird die Zeichenfolge akzeptiert. Mit anderen Worten, mit einem DFA fragen Sie: "Ist der von meiner Eingabe erreichte Zustand ein Akzeptanzzustand?", Während Sie mit einem NFA fragen: " Ist ein Zustand , der von meiner Eingabe erreicht werden könnte, ein Akzeptanzzustand?".

Harrison Paine

8

Nehmen wir zum Beispiel diesen Automaten, es ist ein NFA und er akzeptiert den String . Um pedantischer zu sein, werden Zeichenfolgen akzeptiert, die mit enden . $0110$ $10$

Um zu sehen, müssen wir nur prüfen, ob es einen Akzeptanzstatus erreicht.

\begin{aligned} q_{0} & \to 1 \\ q_{0} & \to 0 \\ q_{1} & \to 1 \\ q_{2} & \to 0 \end{aligned}

$\begin{align*} q_0 & \rightarrow 1\\ q_0 & \rightarrow 0\\ \color{red}{q_1} &\rightarrow \color{red}{1}\\ q_2 &\rightarrow 0\\ \end{align*}$

Jetzt in der roten Linie gab es eine andere Möglichkeit, nämlich beim Lesen der zweiten könnte ich in bleiben und dann in bleiben, wenn ich die letzte lese . Automaten haben keinen Speicher, daher gibt es keine Möglichkeit, einen Status zu speichern und später zu überprüfen, ob meine Zeichenfolge mit endet $1$ $q_0$ $q_0$ $0$ $10$ $10$

Es ist einfacher, eine NFA zu erstellen als eine DFA. Das Gute ist, dass beide gleichwertig sind .

Aristu
quelle

Ja, ich kenne den theoretischen Teil von NFA. Ich habe jedoch gefragt, obgleich es mehrere Übergänge für ein einzelnes Eingabezeichen gibt, ist die Maschine deterministisch in Bezug auf alle Zustände, die sie erreichen kann (z. B. durch das Erstellen von Threads). Daher ist es buchstäblich DFA. [Oder glaubst du, ich interpretiere die Bedeutung des Determinismus falsch

?

1

Das Beispiel könnte mit einem etwas komplizierteren NFA verbessert werden, da ein DFA für denselben Zweck die gleiche Anzahl von Status verwendet wie Ihr NFA und nicht besonders kompliziert wäre. Im Gegensatz dazu erfordert der Abgleich eines komplizierteren regulären Ausdrucks möglicherweise einen komplizierten und unübersichtlichen DFA, ist jedoch in einem NFA trivial.

Supercat

ε

$\varepsilon$

1

@Aristu Wenn Sie eine NFA in Ihrer bevorzugten Programmiersprache implementieren, sind Threads eine schreckliche Wahl. Stattdessen sollten Sie nur den Satz von Zuständen verfolgen, in denen sich der Automat nach dem Lesen der einzelnen Eingabezeichen möglicherweise befindet. Der resultierende Code ist fast so schnell wie eine Implementierung von DFAs.

David Richerby

1

ϵ

$\epsilon$

5

Die Übergangsfunktion eines NFA gibt die zulässigen Übergänge zu jedem Zeitpunkt an. Es könnte mehr als eine Option geben, und die NFA wählt einen nicht deterministischen Übergang mit dem Ziel, schließlich einen akzeptierenden Zustand zu erreichen.

Vielleicht sollten Sie warten, bis Sie etwas über nichtdeterministische Turingmaschinen erfahren. Nichtdeterminismus bedeutet in beiden Fällen dasselbe.

Yuval Filmus
quelle

können Sie bitte hervorheben, dass "ein Übergang nicht deterministisch". Und bitte überprüfen Sie meine Antwort

Madhusoodan P

Ich denke, unsere beiden Antworten sind nicht besonders gut, obwohl Ihre Intuition gut ist.

Yuval Filmus

3

Beginnen Sie mit einem endlichen Automaten. Es hat Zustände und Akzeptanzzustände und Übergänge.

Geben Sie nun mehr als eine Übergangsregel für jeden Staat an und sagen Sie, dass sie akzeptiert, wenn es eine Reihe von Übergangsregeln gibt, die nachträglich ausgewählt werden die Führung der Akzeptanzzustand eine Eingabezeichenfolge gegeben.

Sobald Sie Ihre Eingabezeichenfolge haben, gibt es einen festen Satz konkreter Übergänge und es wird (nacheinander) angegeben, dass diese Zeichenfolge akzeptiert werden soll. Welche Übergänge es auswählt, wird jedoch erst am Ende der Zeichenfolge ausgewählt . Während des Lesens der Zeichenfolge wird nicht festgelegt, welcher Pfad verwendet werden soll.

Es ist nicht deterministisch. Es kann seinen Pfad durch das Diagramm wählen, nachdem Sie ihm das gesamte Problem gegeben haben, und nicht, während es die Eingabe liest.

Nun, wir formalisieren dies anders als dieses Gedankenexperiment, aber dies gibt Ihnen Motivation, warum es diesen Namen bekam.

Dies erklärt, wie es überhaupt zu dem Namen kam. Ja, Sie können NDFA vollständig deterministisch modellieren, aber die Namen sind nicht eindeutig . Sobald Sie etwas Bob angerufen haben, entstehen Kommunikationskosten, wenn Sie es in etwas anderes umbenennen, da niemand weiß, wovon Sie sprechen, wenn Sie es Alice nennen.

Yakk
quelle

Ja! Ich stimme Ihrer Erklärung zu NFA zu. Aber meine Frage ist, warum es nicht deterministisch ist, obwohl die Menge der Zustände für eine einzige Eingabe definiert sind

Madhusoodan P

@MadhusoodanP Es heißt nicht deterministisch, weil es so erfunden / gedacht wurde. Und Namen sind klebrig, auch wenn wir mehrere vollständig deterministische Möglichkeiten zur Modellierung definiert haben.

Yakk

1

Aus Wikipedia ist es am besten, mit deterministischen Finite-State-Maschinen (DFA) zu beginnen. Bei einem DFA wird jeder Übergang eindeutig durch den aktuellen Status und das zu verarbeitende Eingabesymbol bestimmt. Nichtdeterministische Zustandsautomaten (NFA) sind einfach das, was Sie erhalten, wenn Sie diese Determinismusregel lockern, um zuzulassen, dass Übergänge nicht eindeutig definiert werden. Dies erhalten Sie, wenn Sie die Determinisim-Regel aus DFAs entfernen.

Cort Ammon - Setzen Sie Monica wieder ein
quelle

Es ist etwas komplizierter, da Nichtdeterminismus auch eine spezifische Akzeptanzbedingung ist.

Yuval Filmus

1

NFA und DFA werden beide verwendet, um (unter anderem) bestimmte Zeichenfolgen zu erkennen.

Nicht deterministischer endlicher Automat funktioniert so, als hätte er Einfluss auf seine Entscheidungen - er kann "wählen", ob er einem Pfad folgt oder nicht.

Beachten Sie, dass es in der obigen Abbildung, wenn es sich um die Zeichenfolge "00111" handelt, zwei Möglichkeiten gibt, der ersten "1" zu begegnen. Man kann bei "p" bleiben oder zu "q" gehen. Wenn sich die Automaten auf das "q" bewegen sollten, würde sie die Zeichenfolge nicht akzeptieren (da aus dem "q" keine Kanten herauskommen). Aber die Zeichenkette kann von diesen Automaten akzeptiert werden, indem sie nur mit der letzten 1 zum "q" wechselt, während sie für alles andere auf "p" bleibt (und genau das passiert).

NFA lässt es so aussehen, als ob die Automaten "wüssten", was vor ihnen liegt, und wählt entsprechend aus.

Natürlich nicht. DFA und NFA sind in Bezug auf die Leistung gleichwertig (Sie können NFA auf DFA reduzieren und DFA (wahrscheinlich) durch Verwendung von NFA vereinfachen), aber NFA ist nützlich, da es ermöglicht, die gleichen Sprachen wie DFA zu definieren und dabei die Diagramme weitgehend beizubehalten kürzer und lesbarer.

Da ist nichts Zufälliges drin. Der nicht deterministische Teil betont die Tatsache, dass es eine "Wahl" gibt, aber die Wahrheit ist, dass die Automaten keine Entscheidungen treffen.

MatthewRock
quelle

0

Nun, hier ist die Mischung aus einigen Inhalten aus Buch [Einführung in formale Sprachen und Automaten von Peter Linz 4E] und meinem Verständnis.

Stellen Sie sich ein Spielprogramm vor, in dem die Maschine die Entscheidung für den nächsten Zug treffen muss [z. B. für Tic-Tac-Toe]. Da mehrere Züge möglich sind, wählen wir jeden Zug deterministisch aus und werten den Zug aus und entscheiden uns für den besten. Obwohl der Auswahlprozess deterministisch war und es viele mögliche Züge gab, war der endgültige Zug ein einziger und wurde als bester Zug ausgewählt, während alle erprobten Zugberechnungen vor dem Gegner verborgen wurden. [Hier nehmen wir an, dass der Bewertungsprozess für jeden möglichen Zug vor dem Gegner verborgen war].

Daher wurde nur eine Wahl getroffen und dem Gegner wird eine Illusion gegeben, dass der Zug nicht deterministisch war.

Nun, wenn Sie noch nicht überzeugt sind, dass der beste Zug das Produkt einiger deterministischer Berechnungen war, müssen Sie die Maschine in Betracht ziehen, die vollkommen zufällige Züge ausführt (es kann sein, dass die Maschine verliert, aber es ist eine NFA).

Madhusoodan P
quelle

1

Eine andere Art, dies auszudrücken: Dem Gegner gegenüber war Ihre Wahl nicht deterministisch. Wenn Sie das System aus der Sicht des Gegners modellieren, ist Ihr Zug eine nicht deterministische Wahl, es sei denn, der Gegner hat den deterministischen Prozess dahinter herausgefunden.

Reinierpost

@reinierpost genau das, was ich sagen wollte

Madhusoodan P

Ein interessanteres Beispiel könnte ein bewegliches Spiel mit begrenzten Informationen sein (zB "Cops and Robbers" -Stil). Ein Spieler bewegt einen Räuber um ein Labyrinth, während der andere Spieler Polizisten bewegt. Zu jeder Zeit, wenn ein Cop einen Räuber sehen kann, ist der Status des Räubers sein Standort. Wenn jedoch keiner der Cops den Räuber sieht, kann der Räuber zu einem beliebigen Feld übergehen, das sich neben seiner Position befindet und das die Cops sehen können sehe ich gerade nicht.

Supercat

@supercat Schön, aber Übergang gemacht ist immer ein einziger Zustand, und wenn Sie die Berechnung des besten Zuges verbergen, scheint es nicht deterministisch

Madhusoodan P

Warum heißt NFA nicht deterministisch?

Antworten: