Home -> Themen -> nicht-deterministischer Kellerautomat


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 nicht-deterministische Kellerautomaten

Download aller Beispiele
zur Simulation mit Turing-Werkstatt.exe

Beispiel1, deterministisch
Ein deterministischer Kellerautomat KA1, der
L = {Wort c WortR | Wort aus {a,b}*} erkennt.
WortR entsteht aus Wort durch Rückwärtslesen. Der Automat kellert alle Symbole auf dem Stapel ohne den Zustand Z0 zu wechseln, bis er auf ein 'c' trifft. Nach Lesen des 'c' geht er in Z1 über. In Z1 verbleibt er nun und vergleicht das aktuelle Eingabesymbol mit dem obersten Zeichen auf dem Stapel. Stimmen diese überein, so wird das oberste Zeichen des Stapels entfernt. Die Eingabe ist akzeptiert, wenn sie vollständig verarbeitet und der Kellerspeicher geleert und der Zustand Z1 erreicht wurde.

ka1

Das Bild zeigt den Kellerautomaten ka-wcwr.tm bei der Verarbeitung des Wortes abcba. Man kann diese Situation durch ein Wort beschreiben :
[AB -Z0- cba   <-->   Kellerspeicherinhalt - aktueller Zustand - Eingaberest

Verlauf der Verarbeitung von 'abcba' :
trace

Bei dieser Notation der Konfigurationen bedeutet die Anwendung eines Befehls die Anwendung eine der fünf folgenden Ersetzungsregeln. Dieser KA ist deterministisch, da in keinem Fall zwei der Ersetzungsregeln gleichzeitig anwendbar sind.

tabelle

Bei nicht-deterministischen Kellerautomaten lässt man zu, dass dem KA mehrere Befehle in einer Situation zur Verfügung stehen und dass er dann im weiteren Verlaufe der Verarbeitung der Eingabe die verschiedenen Alternativen parallel verarbeitet. Für die Darstellung der Konfigurationen durch jeweils ein Wort bedeutet das, dass man in einem Schritt aus einem Konfigurationswort durch Anwendung der möglichen Ersetzungsregeln mehrere Folgewörter erhalten kann. Machen wir uns das an einem Beispiel klar.

Beispiel2, nicht-deterministisch
Ein nicht-deterministischer Kellerautomat KA2, der L = {Wort WortR | Wort aus {a,b}*} erkennt. KA2 arbeitet wie der deterministische KA1 aus Beispiel 1. Allerdings hat er die Schwierigkeit, dass er nicht wissen kann, wann die Hälfte der Eingabe erreicht ist, denn das Zeichen 'c' für die Mitte fehlt bei den gesuchten Wörtern. Der KA muss also in jeder Situation vermuten, dass der Übergang von Z0 nach Z1 nötig sein kann. Im Unterschied zu Beispiel 1 entfällt die Ersetzungsregel:   -Z0-c   ->   -Z1-  . Statt dessen ist im Zustand Z0 jederzeit ein Übergang in Z1 möglich ohne Verbrauch eines Symbols der Eingabe. Dafür sorgt die neue Ersetzungsregel :   -Z0-   ->  -Z1-
Die Tabelle zeigt alle Ersetzungsregeln für KA2
trace
In Turing-Werkstatt.exe kann man zwar die Befehle in die Tafel der Maschine eintragen. Allerdings wird der dritte gefärbte Befehl nie ausgeführt, da er in Konkurrenz zu den ersten beiden Befehlen steht, die bevorzugt sind, da sie weniger Jokerzeichen enthalten. Die Jokerzeichen '?' und '!' stehen dabei für jedes beliebige Zeichen. Betrachten wir die Abfolge der Konfigurationen bei der Verarbeitung des Wortes w=abba.
tabelle
Die fett gedruckten Wörter bilden die Konfigurationsfolge, die zur Akzeptanz des Wortes führen.

Simulation von Kellerautomaten
Deterministische KA können direkt mit dem Turing-Werkstatt.exe simuliert werden. Siehe Kapitel Kellerautomat . Bei nicht-deterministischen KA ist das so nicht möglich. Wir müssten damit rechnen, dass bei jedem Verarbeitungsschritt weitere unterschiedliche Stapelinhalte, Zustände und Eingabereste entstehen und verwaltet werden müssen. Als Ausweg bietet sich die Verwendung der Konfigurationswörter an wie sie oben beschrieben ist. Auf entsprechende Weise können auch weitere nicht-deterministische Maschinen simuliert werden, so zum Beispiel Turing-Maschinen mit einem Band oder endliche Automaten ohne Ausgabe.
Vorgehensweise :
Gegeben ist das Wort für die Anfangskonfiguration. Auf dieses wendet man alle möglichen Ersetzungsregeln an, die dem KA zur Verfügung stehen, und erhält so alle Folgekonfigurationen. Diese werden mit der akzeptierenden Endkonfiguration verglichen. Ist die akzeptierende Endkonfiguration erreicht, stoppt der KA und das Eingabewort ist akzeptiert. Andernfalls wird das Verfahren mit den neuen Konfigurationen fortgeführt.

KA-Akzeptor.tm simuliert alle Kellerautomaten
KA-Akzeptor.tm stimmt überein mit L(G)-Akzeptor.tm . L(G)-Akzeptor.tm ist eine dreibändige Turing-Maschine mit der man untersuchen kann, ob ein vorgegebenes Wort aus dem Startsymbol mit den Ersetzungsregeln einer Regelgrammatik G erzeugt werden kann. Um L(G)-Akzeptor.tm für unsere Zwecke zu verwenden, führt man folgende Änderungen durch :
Band 1 enthält die akzeptierende Endkonfiguration gefolgt von einer Leerstelle und den Ersetzungsregeln, die voneinander durch Kommata getrennt sind,
Band 2 enthält die Anfangskonfiguration mit dem Eingabewort.
Band 3 bleibt leer.

Hinweise zur Verwendung von KA-Akzeptor.tm
Zur Veranschaulichung laden Sie KA-Akzeptor.tm in Turing-Werkstatt.exe. Die Eingaben zur Simulation des nicht-deterministischen KA, der L = {Wort WortR | Wort aus {a,b}*} erkennt, sind bereits eingegeben. Auf Band1 sind akzeptierende Endkonfiguration und die Ersetzungsregeln, auf Band2 die Anfangskonfiguration [-z0-abbbba eingetragen.
screen
Stellen Sie den Sprungmodus ein. Mit jedem Sprung erscheinen auf Band 2 die nächsten Folgekonfigurationen. In 7 Sprüngen ist die akzeptierende Endkonfiguration erreicht. Die Anzahl der Sprünge stimmt mit dem Aufwand überein, wie er in der theoretische Informatik definiert ist. Sie können andere Worte bearbeiten, indem Sie die Startkonfiguration auf Band 2 ändern. Wenn Sie andere KA simulieren wollen, müssen Sie in Band 1 die entsprechenden Ersetzungsregeln für die Folgekonfigurationen ändern.

Übungen
1) Realisieren Sie einen nicht-deterministischen Kellerautomaten,der die Menge der Palindrome über {a,b} erkennt. Ein Palindrom ändert sich nicht wenn man es rückwärts liest. Der Automat aus Beispiel 2 erkennt bereits Palindrome mit einer geraden Anzahl von Buchstaben. Sie müssen nur für den Fall, dass die Eingabe aus einer ungeraden Anzahl von Buchstaben besteht, weitere Ersetzungsregeln hinzunehmen.

2a) L = {ambncn | m,n aus N} soll durch einen deterministischen Kellerautomaten erkannt werden.
2b) L = {ambncn oder anbncm | m,n aus N} soll durch einen nicht-deterministischen Kellerautomaten erkannt werden.


Letzte Änderung : 15.3.2016