Entspricht ein Push-Down-Automat mit zwei Stapeln einer Turing-Maschine?

41

In dieser Antwort wird es erwähnt

Eine reguläre Sprache kann von einem endlichen Automaten erkannt werden. Für eine kontextfreie Sprache ist ein Stapel erforderlich, und für eine kontextsensitive Sprache sind zwei Stapel erforderlich (dies entspricht der Angabe, dass eine vollständige Turing-Maschine erforderlich ist) .

Ich wollte über die Wahrheit des kühnen Teils oben wissen. Ist es tatsächlich wahr oder nicht? Was ist ein guter Weg, um eine Antwort darauf zu finden?

computability turing-machines automata pushdown-automata Laser
quelle
Der fett gedruckte Text enthält zwei Behauptungen, aber Ihr Fragentitel deutet darauf hin, dass Sie nur an einer dieser Behauptungen interessiert sind.
Tyson Williams
@TysonWilliams: ja, also?
Lazer
Das ist verwirrend. Ich weiß nicht, für welche Teilmenge der beiden Behauptungen Sie eine Rechtfertigung wünschen.
Tyson Williams
Für den in Fettdruck , wie in der Frage erwähnt.
Lazer
2
@Lazer: Der fett gedruckte Text enthält zwei Anweisungen ("CSL erfordert zwei Stapel", "zwei Stapel entsprechen TM"). Da CSL eine richtige Teilmenge von RE ist, kann nur eine wahr sein.
Raphael

Antworten:

38

Zwei Bits zu dieser Antwort;

Erstens ist die von Turing Machines erkannte Sprachklasse nicht kontextsensitiv , sondern rekursiv aufzählbar (kontextsensitiv ist die Sprachklasse, die Sie von linear gebundenen Automaten erhalten ).

Der zweite Teil, vorausgesetzt, wir korrigieren die Frage, lautet: Ja, ein Zwei-Stapel-PDA ist so leistungsfähig wie ein TM. Es ist etwas einfacher anzunehmen, dass wir ein TM-Modell mit einem Band verwenden, das nur in einer Richtung unendlich ist (obwohl beide Richtungen nicht viel schwieriger und gleichwertiger sind).

Um die Äquivalenz zu sehen, stellen Sie sich den ersten Stapel als den Inhalt des Bands links von der aktuellen Position und den zweiten als den Inhalt rechts vor. Sie fangen so an:

  • Drücken Sie auf beide Stapel die normalen Markierungen für den Stapelboden.
  • Schieben Sie die Eingabe in den linken Stapel (verwenden Sie Nicht-Determinismus, um das Ende der Eingabe zu "erraten").
  • Bewegen Sie alles auf den richtigen Stapel (um die Dinge in der richtigen Reihenfolge zu halten).

Jetzt können Sie die Eingabe ignorieren und alles auf den Inhalten der Stapel (die das Band simulieren) tun. Sie springen zum Lesen und drücken zum Schreiben (so können Sie das "Band" wechseln, indem Sie etwas anderes drücken, als Sie gelesen haben). Dann können wir das TM simulieren, indem wir vom rechten Stapel springen und nach links drücken, um nach rechts zu gehen, und umgekehrt, um nach links zu gehen. Wenn wir den unteren Rand des linken Stapels erreichen, verhalten wir uns entsprechend (anhalten und ablehnen oder je nach Modell dort bleiben, wo Sie sind). Wenn wir den unteren Rand des rechten Stapels erreichen, drücken wir einfach ein leeres Symbol nach links.

Einen vollständigen formalen Beweis finden Sie in der Antwort auf eine andere Frage .

Der umgekehrte Zusammenhang sollte noch offensichtlicher sein, dh wir können einen Zwei-Stapel-PDA mit einem TM simulieren.

Luke Mathieson
quelle