Ich erkenne, dass nicht deterministische Pushdown-Automaten eine Verbesserung gegenüber deterministischen darstellen können, da sie unter mehreren Zuständen "wählen" können und es einige kontextfreie Sprachen gibt, die von einem deterministischen Pushdown nicht akzeptiert werden können.

Trotzdem verstehe ich nicht, wie genau sie "wählen". Für Palindormes sagt zum Beispiel jede Quelle, die ich gefunden habe, nur, dass der Automat die Mitte des Wortes "errät". Was bedeutet das?

Ich kann mir mehrere mögliche Bedeutungen vorstellen:

1. Es geht zufällig in einen Zustand über und akzeptiert daher möglicherweise kein Wort, das tatsächlich in der Sprache ist

2. Es geht irgendwie "auf jede mögliche Weise". Wenn also der erste falsch ist, wird geprüft, ob einer der anderen richtig sein könnte

3. Es gibt einen Mechanismus, den ich nicht kenne, der die Mitte des Wortes wählt und daher nicht zufällig ist, aber der Automat findet immer die richtige Mitte.
   

Dies ist nur ein Beispiel. Was ich wissen möchte, ist, wie es für jeden Automaten funktioniert, der mehrere folgende Zustände für ein und denselben Zustand vor sich hat.

Der Mechanismus ist ganz einfach magisch. Die Idee des Nichtdeterminismus ist, dass er einfach weiß, welchen Weg er einschlagen muss, um das Wort zu akzeptieren, und das geht auch so. Wenn es mehrere Möglichkeiten gibt, geht es um eine davon.

Nichtdeterminismus kann nicht als solcher in echte Hardware implementiert werden. Wir simulieren es mit Techniken wie Backtracking. In erster Linie handelt es sich jedoch um ein theoretisches Gerät, mit dem die Darstellung bestimmter Konzepte vereinfacht werden kann.

Für das Palindrom gibt es zwei Möglichkeiten, darüber nachzudenken. Entweder gibt es eine magische Kraft, die Ihre Maschine sagen lässt: "Dies ist die Mitte des Wortes, Zeit, um vom Drücken zum Knallen zu wechseln." ist die Mitte des Wortes, und prüfen Sie, ob es sich um ein Palindrom handelt. In diesem anderen Thread werde ich es weiter versuchen, vorausgesetzt, dies ist nicht die Mitte des Wortes ".

Eine andere Sichtweise ist die unendliche Parallelität. Ein äquivalentes Modell wäre also, dass statt eines neuen Pfades beide Pfade gleichzeitig ausprobiert werden und neue "Prozesse" abgezweigt werden, die, wenn überhaupt, in einem Endzustand sind, nachdem das ganze Wort gelesen wurde. Auch dies kann nicht mit echter Hardware erstellt werden, sondern kann mit Nichtdeterminismus modelliert werden.

Das Interessante am Nicht-Determinismus ist, dass er für Automaten und Turing-Maschinen nicht deren Rechenleistung erhöht, sondern lediglich deren Effizienz.

Der Hauptunterschied (meiner Meinung nach) zwischen einem deterministischen und einem nicht deterministischen Automaten besteht darin, dass für einen deterministischen Automaten ein bestimmtes Eingabewort nur einen Pfad durch die Maschine hat. In einem nicht deterministischen Automaten kann ein gegebenes Eingabewort mehrere Wege durch die Maschine haben (weil an einigen Punkten eine Wahlmöglichkeit bestehen kann).

Vor diesem Hintergrund muss auch die Bedingung für die Annahme eines Eingabeworts geändert werden, um der Tatsache Rechnung zu tragen, dass ein Wort mehrere Pfade durch die Maschine führen kann. Die übliche Definition der Akzeptanz für einen nicht deterministischen Automaten lautet wie folgt: Damit ein Wort vom Automaten akzeptiert werden kann, muss es mindestens einen Akzeptanzpfad geben, der durch dieses Wort induziert wird.

Dies führt dann zu der Idee eines Automaten "erraten", wenn ein Wort von einem nicht deterministischen Automaten akzeptiert wird, dann neigen wir dazu, den Automaten als automatisch die richtigen Entscheidungen zu treffen, so dass einer der akzeptierenden Pfade wird befolgt, wenn dieses Wort als Eingabe dargestellt wird.

Für Palindrome bedeutet dies, dass der PDA im Wesentlichen zwei Modi hat: einen Push-Modus, in dem die aktuellen Buchstaben auf dem Stapel abgelegt werden, und einen Popping-Modus, in dem diese Buchstaben entfernt und mit der Eingabe abgeglichen werden. Diese Maschine hat einen leeren Übergang vom Druckzustand zum Knallzustand, dem sie an jedem Punkt des Wortes folgen kann. Die Maschine leert jedoch nur dann ihren Stapel und wechselt in einen Akzeptanzzustand, wenn sie ein Palindrom gelesen hat und dem Leerübergang in der Mitte des Palindroms gefolgt ist. Da wir nur die Existenz eines Akzeptanzpfades benötigen, können wir sagen, dass der Automat "errät", wo sich die Mitte des Wortes befindet.

Die Idee des Nichtdeterminismus ist recht einfach: Der Automat kann in bestimmten Situationen mehrere nächste Schritte haben. Der Automat akzeptiert, wenn es eine (möglicherweise mehrere!) Abfolge von Schritten gibt, die von der Erstkonfiguration zu einer akzeptierenden führen, und lehnt nur ab, wenn keine vorhanden sind solche Abfolge gibt.

Dies bedeutet, dass es "entscheidet", welcher Schritt in diesen mehrdeutigen Situationen als nächstes zu unternehmen ist. Eine Möglichkeit, darüber zu sprechen, besteht darin, es magisch auszudrücken den "richtigen" nächsten Schritt auswählt (oder einen, wenn es mehrere "richtige" Schritte gibt). Eine andere Möglichkeit besteht darin, dass sich die Berechnung des Automaten in solchen Situationen in mehrere Kopien aufteilt, von denen jede einen Pfad verfolgt.

In der Praxis kann dies durch Zurückverfolgen implementiert werden, indem eine Art Tag an den Stellen platziert wird, an denen die Entscheidung getroffen wurde, und wenn der aktuelle Pfad nicht funktioniert, gehen Sie zurück und probieren Sie die nächste Alternative aus. Dies wird normalerweise durch Rekursion erledigt. Oder Sie ergänzen die Informationen, über die der Automat "legal" verfügt, mit zusätzlichen Informationen (das tun Sie, wenn Sie zeigen, wie ein nicht deterministischer Automat an der Tafel funktioniert, nach vorne schaut und herausfindet, welcher der Schritte zum Erfolg führt).

"Erraten" steht in direktem Zusammenhang mit unserer existenziellen Interpretation des Nichtdeterminismus

Auf den Punkt gebracht: Diese Vorstellung, dass ein nicht deterministischer Automat erraten (oder von einem Orakel unterstützt werden kann), hängt direkt mit unserer existentiellen Interpretation des Nichtdeterminismus zusammen. Eine andere Interpretation ist möglich (vielleicht auch andere), wenn "raten" keinen Sinn ergibt.

Nichtdeterminismus ist seltsam. Wir haben eine Möglichkeit, sie in der Automatentheorie zu interpretieren, aber es ist nicht von vornherein klar, wie wir das tun sollen.

Es mag überraschend erscheinen, aber Nichtdeterminismus ist eine sehr häufige Situation. Wenn man einen Satz unter Berücksichtigung der Axiome einer mathematischen Theorie beweisen muss, ist der Prozess natürlich nicht deterministisch. Deshalb wissen wir oft nicht, was wir tun sollen, um ein Problem zu lösen, zum Beispiel um die Lösungen einer Gleichung dritten Grades zu finden oder einen Satz zu beweisen.

Es gibt viele Möglichkeiten, das Bekannte mit Inferenzregeln zu kombinieren, um neue Ergebnisse zu erzielen. Und die Situation ist normalerweise die gleiche, wenn wir versuchen, einen Beweis aus dem Ergebnis rückwärts zu rekonstruieren.

Wenn wir versuchen, ein solches Problem zu lösen, versuchen wir, einen Pfad in einem Übergangssystem zu " erraten " .

Tatsächlich raten wir nicht, sondern bauen in unserem Geist eine Struktur auf, die das Labyrinth der Möglichkeiten organisiert und / oder vereinfacht, damit wir unseren Weg durch das Labyrinth sehen können. In einigen Fällen folgt die Frage einem identifizierten Muster, für das wir (manchmal? Normalerweise? Immer?) Einen Standardweg haben, um eine Lösung zu finden, und wir nennen das einen Algorithmus.

Eine (normalerweise teure) Technik, die wir anwenden können, besteht darin, das Labyrinth vollständig zu erkunden: Alle Pfade zu befolgen, wobei die Breite zuerst eingehalten wird, um nicht in einem unendlichen Teilgraphen gefangen zu werden. Das ist ziemlich viel , was getan wird, verzahnt alle möglichen Berechnungen eines nicht-deterministischen Automaten. Diese abgeleitete verzahnte Berechnung ist selbst eine deterministische.

$DC$$A$$A$$A$ niemals anhält oder niemals mit Akzeptanz anhält.

Tatsächlich könnte es verschiedene Arten geben, eine nicht deterministische Berechnung zu interpretieren . Afaik sie sind alle konsistent, aber nicht miteinander.

$R$$w$ . Dies steht im Einklang mit unserer eigenen Ansicht über den nicht deterministischen Beweisprozess, der als erfolgreich angesehen wird, wenn er einen Beweisbaum für den zu beweisenden Satz identifizieren kann.

Die Idee, für den Erkenner zu raten, ist nur ein Bild, das aus unserer eigenen Art des "Ratens", wie man diesen Beweisbaum findet, stammt. Aber der große Unterschied ist, dass unser Gehirn kein PDA ist. Es handelt sich um viel komplexere Geräte mit der Fähigkeit, Übergangsstrukturen näherungsweise zu untersuchen und abzubilden, damit wir uns durch sie hindurchbewegen können, was wir manchmal als Vermutung empfinden.

Diese Interpretation der nicht deterministischen Berechnung würde ich als existentielle Akzeptanz bezeichnen , da nur die Existenz einer einzigen akzeptierenden Berechnung erforderlich ist. Es entspricht einem existenziellen Stillstand , den ich in einer anderen Antwort eingeführt habe .

Man könnte den Nichtdeterminismus jedoch auch universell interpretieren als: Ein Erkenner soll (universell) eine Eingabe "w" akzeptieren, wenn alle möglichen Berechnungen anhalten und die Eingabe akzeptieren. Diese universelle Akzeptanz entspricht dem in derselben Antwort eingeführten Konzept des universellen Stillstands.

Universelle Akzeptanz und universelles Anhalten scheinen zu einem selbstkonsistenten Verständnis des Nichtdeterminismus zu führen. Man könnte also mit dieser Definition theoretisch arbeiten. Aber es entspricht nicht unserer üblichen Praxis in vielen nicht deterministischen Situationen, wie sie ein Theorem beweist, oder in alltäglichen Situationen. Wenn wir mit einem Problem konfrontiert werden, wollen wir nur einen Weg, es zu lösen, und dann ist es uns egal, ob andere Wege erfolgreich sind oder nicht (nun, das ist etwas zu vereinfacht).

Wenn wir ein Palindrom erkennen müssen, können wir es erraten, indem wir die Länge messen und nach der Mitte suchen. Der PDA kann nicht. Da wir jedoch nur an der Existenz einer Lösung interessiert sind, können wir immer so tun, als ob dies der Fall wäre. Oder wir können davon ausgehen, dass es Orakel gibt, die von intelligenteren Maschinen (uns?) Bereitgestellt werden, um ihm zu helfen. Oder Sie können es sogar als Magie bezeichnen und glauben, dass dies der Fall ist (schließlich ist der existenzielle Quantifizierer eine Art Zauberstab). Wenn es helfen kann, wird es helfen. Wenn es keine akzeptierende Berechnung gibt, wird keinerlei Hilfe von Nutzen sein.

Beachten Sie, dass diese Idee des Erratens in der universellen Akzeptanzinterpretation bedeutungslos wäre.