Unterscheidet sich der Nichtdeterminismus in einer nicht deterministischen Turingmaschine von dem von endlichen Automaten und Push-Down-Automaten?

9

Es sei eine Eingabezeichenfolge als . Befindet sich eine NFA derzeit im Zustand (und hat die Eingabe bis zum Alphabet ), teilt sich die NFA vor dem Lesen des nächsten Eingabesymbols in zwei NFA auf, von denen sich eine im Zustand und die andere in , wenn ein Übergang von der Typ . Wenn es einen Zyklus vom Typ , wobei q_i einige Zustände von NFA sind, dann ist es sinnlos, sich an einen anderen NFA im Zustand r bis zu dem Punkt zu erinnern, an dem die Eingabe bis zum Alphabet w_i gelesen wurde r w i r s r & egr; s r & egr; s & egr; q 1 . . . . ϵ q k ϵ r q iw1w2...wnrwirsrϵsrϵsϵq1....ϵqkϵrqiw irwi.

Wenn sich ein PDA (nicht deterministisch) im Zustand r (und die Eingabe bis w_i gelesen wirdwi ) und ein Zyklus rϵ,ϵasϵ,ϵaq1....ϵ,ϵaqkϵ,ϵar (wobei Übergang ϵ,ϵa bedeutet, dass nichts nach wi wird von der Eingabe gelesen, nichts wird gepoppt oder vom Stapel gelesen und das Alphabet a wird auf den Stapel geschoben), dann gibt es vor dem Lesen des nächsten Eingabealphabets wi+1 einen unendlichen PDA in den Zuständen r,s,q1,...qk denn anders als bei der NFA können die Zustände, obwohl sie endliche Stapelinhalte sind, unterschiedlich sein (unendliche Möglichkeiten), wenn ich mich nicht irre.

Wie bei NFA und PDA kommt die Kraft des Nichtdeterminismus von ϵ Übergängen. Ich gehe also davon aus, dass die nicht deterministische Turing-Maschine ihren Nicht-Determinismus auch durch ϵ Übergänge wie NFA und PDA (eher wie PDA) erhält . Ich weiß, dass eine deterministische Turing-Maschine eine nicht deterministische simulieren kann (ich kenne den Beweis, der die Brotsuche verwendet). Aber jetzt bin ich zweifelhaft, wie das möglich ist. Denn wenn im Zustandsdiagramm der nicht deterministischen Turingmaschine ein Zyklus vom Typ in PDA oben existiert, dann vor dem Lesen des nächsten Symbols wi+1Die deterministische Turing-Maschine müsste selbst dann, wenn sie eine Konfiguration in einem Zweig einer nicht deterministischen Turing-Maschine simuliert (während bfs), die unendliche Turing-Maschine verfolgen (wieder sind die Zustände endlich, aber die Symbole auf dem Band haben unendliche Möglichkeiten).
Wie genau ist der Nichtdeterminismus bei Turing-Maschinen definiert? Verstehe ich etwas Triviales falsch? Verwenden nicht deterministische Turing-Maschinen ϵ Übergänge?


Es tut mir leid für meine trivialen Zweifel. Wenn etwas nicht stimmt, kann ich meine Frage aktualisieren.

Sashas
quelle
2
In Bezug auf die Titelfrage gibt es keinen großen Unterschied in den formalen Definitionen. Ja, die austretende Kraft hat in jedem Maschinenmodell sehr unterschiedliche Auswirkungen. Was den Rest der Frage betrifft, fällt es schwer, sie zu analysieren. :(
vzn
1
Hast du Wikipedia überprüft? en.wikipedia.org/wiki/Non-deterministic_Turing_machine
Yuval Filmus
@ YuvalFilmus ja ich habe. Die Definition der Übergangsfunktion beinhaltet einen Leistungssatz, den ich verstehe. Aber die Sache mit Übergängen in Turing-Maschinen ist mir immer noch unklar. epsilon
Sashas
@vzn Ich dachte schon. Es tut mir echt leid. Ich bin schlecht darin, meine Zweifel vorzubringen. Aber ich kann mich verbessern, wenn Sie Vorschläge machen.
Sashas

Antworten:

8

Nichtdeterminismus ist in allen Kontexten dasselbe Konzept - die Maschine kann an jedem Punkt mehrere Optionen ausführen. Jedoch sind die Semantiken etwas anders , da DFAs / NFAs und PDAs immer definieren Gesamtfunktionen, während Turing Maschinen (deterministisch oder nicht deterministisch ) im allgemeinen definieren Teilfunktionen.

Eine Teilfunktion ist eine Funktion, die nur für einen Teil der Domäne definiert ist. Wenn auf nicht definiert ist, schreiben wir . (Also ist wirklich eine Gesamtfunktion, aber es gibt ein spezielles Element im Bereich, das anzeigt, dass die Ausgabe undefiniert ist.) Eine deterministische Turingmaschine definiert eine Teilfunktion wie folgt: Wenn auf anhält, ist die Inhalt des Bandes, wenn auf anhält ; und ansonsten ist .x f ( x ) = f M M x M ( xfxf(x)=fMMxM x M ( x ) = M(x)MxM(x)=

Eine deterministische Turing Maschine decider hat zwei Arten von Anhaltezustände, die Annahme und Ablehnung, und definiert eine Teilfunktion , wie folgt: wenn stoppt auf in einem Zustand anzunehmen, dann ; wenn es in einem zurückweisenden Zustand anhält, dann ist ; Wenn es nicht anhält, ist . Wenn immer anhält, sagen wir, dass es die Sprache akzeptiert .x M ( x ) = 1 M ( x ) = 0 M ( x ) = M.MxM(x)=1M(x)=0M(x)=ML={x:M(x)=1}

Eine nicht deterministische Turing-Maschine (die immer ein Entscheider ist) darf "verzweigen" (hat zu einem bestimmten Zeitpunkt mehrere mögliche Optionen) und hat die folgende Semantik:

  • x M.M(x)=1 wenn bei Eingabe die Maschine an allen Zweigen anhält und bei einem akzeptierenden Zustand für mindestens einen Zweig anhält.xM
  • x M.M(x)=0 wenn bei Eingabe die Maschine an allen Zweigen anhält und immer in einem Ablehnungszustand anhält.xM
  • x M.M(x)= wenn bei Eingabe ein Zweig existiert, an dem nicht anhält.xM

Angesichts dieser Definition ist hoffentlich klar, wie eine nicht deterministische Turing-Maschine mit einem deterministischen Turing-Maschinenentscheider simuliert werden kann: Sie probieren alle Zweige aus und prüfen, ob einer von ihnen zu einem akzeptierenden Haltezustand führt. Nachdem alle Zweige angehalten wurden, können Sie entscheiden, ob Sie in einen akzeptierenden oder in einen ablehnenden Zustand wechseln möchten. Wenn die nicht deterministische Turing-Maschine nicht an einem Zweig anhält, würde dies auch die deterministische tun.


Was ist mit Bewegungen? Sie verursachen Probleme, da der entsprechende Automat möglicherweise nie anhält. Für endliche Automaten (NFAs und PDAs) ignorieren wir stillschweigend nicht anhaltende Berechnungen. Unser Grund dafür ist, dass die resultierenden Sprachen immer berechenbar sind, obwohl der naive Algorithmus zur deterministischen Simulation (Simulation aller Berechnungspfade) nicht ganz funktioniert. Dies ist für NFAs, die in DFAs konvertiert werden können, nicht so schwierig. Deterministische PDAs sind jedoch streng schwächer als nicht deterministische PDAs. Sie können jedoch zeigen, dass jeder PDA einem ohne Übergänge entspricht (obwohl der Beweis möglicherweise kontextfreie Grammatiken durchläuft).ϵϵϵ

Sie können Bewegungen in Turing-Maschinen simulieren , müssen jedoch darauf achten, dass keine Schleifen vorhanden sind, die nicht anhaltende Berechnungen verursachen. In einigen Fällen können wir jedoch den gleichen Trick wie oben verwenden. Angenommen, Ihre Turing-Maschine ist platzbeschränkt: Wir kennen eine Obergrenze für den verwendeten Speicherplatz (abhängig von der Eingabelänge). In diesem Fall wird jede nicht anhaltende Berechnung notwendigerweise wiederholt (da die Turing-Maschine endlich viele Zustände hat, einschließlich des Bandinhalts). Wenn wir also nicht anhaltende Berechnungen wie oben "ignorieren", ist das resultierende Berechnungsmodell immer noch berechenbar. Im Allgemeinen funktioniert dies, solange garantiert ist, dass jeder Berechnungszyklus nicht angehalten wird. (Dies ist bei NFAs der Fall, nicht jedoch bei PDAs.)ϵ

Yuval Filmus
quelle
Danke. Ich hatte einen letzten Zweifel. Wenn sich in einem PDA mit dem Übergang der PDA im Zustand , wird er nur geteilt, wenn ( ist das vom Eingabeband gelesene Alphabet, ist das vom Stapel abgelegte Alphabet und wird zum Stapeln verschoben) ist unabhängig davon, was und sind ( oder reguläre Stapelalphabete). Habe ich recht ? r b b c a ϵ a c ϵrb,casrbbcaϵacϵ
Sashas
@sasha Die Ausführung "wird aufgeteilt", wenn mehr als eine Option zum Fortfahren vorhanden ist.
Yuval Filmus
Wie gehe ich vor, um zu beweisen, dass ein PDA mit Übergängen in einen ohne sie umgewandelt werden kann? Ich weiß, dass ich immer beweisen kann, dass die von einem PDA akzeptierte Sprache entscheidbar ist, indem ich sie in normaler Chomsky-Form in ihre CFG umwandle. Kann aber immer noch nicht ohne Epsilon-Übergänge auf PDA konvertieren. Ich würde mich über jeden Hinweis sehr freuen. ϵ
Sashas
1
@sasha Sie können eine kontextfreie Grammatik in Greibach-Normalform in einen PDA ohne Übergänge konvertieren (zumindest laut Wikipedia). ϵ
Yuval Filmus
1
@YuvalFilmus, eine nichtdeterministische Konstruktion von GNF ist im Wesentlichen rekursiver Abstieg: Für eine Produktion , wenn oben im Stapel ist, ersetzen Sie bei Eingabe das durch auf dem Stapel . Kein in Sicht. Immer noch nicht deterministisch (es kann mehrere Produktionen geben, die starten ). A a A B 1B n ϵ A a AaB1B2BnAaAB1BnϵAa
vonbrand