Fachkonzept - Turingmaschine
Grundidee
Die Grundidee soll anhand einer Verarbeitungseinheit erläutert werden, die
Klammerausdrücke der Gestalt aabb, die nach einer Anzahl
öffnender a-Klammern genauso viele schließende b-Klammern haben, erkennen kann.
Die gezeigte Verarbeitungseinheit befindet sich stets in einem bestimmten Zustand. Sie verfügt über ein nach rechts und links unbegrenztes Band, auf dem sich zu Beginn das Eingabewort befindet. Die einzelnen Zellen des Bandes können mit einem Lese-/Schreibkopf angesteuert werden. Der Lese-/Schreibkopf kann sich jeweils einen Schritt nach rechts oder nach links bewegen (oder auch stehen bleiben). Er kann den Inhalt einer Zelle lesen und auch Symbole in Zellen schreiben.
Im vorliegenden Fall befindet sich die Verarbeitungseinheit zu Beginn in einem Anfangszustand q0.
Der Lese-/Schreibkopf befindet sich an der Zelle mit dem ersten Symbol des Eingabeworts.
Dieses erste Symbol a wird im ersten Schritt durch ein neues Symbol x erzetzt. Zudem wandert der Lese-/Schreibkopf
einen Schritt nach rechts. Das Nach-Rechts-Bewegen wird solange fortgesetzt, bis eine Zelle mit leerem
Inhalt erreicht wird. Der Lese-/Schreibkopf geht dann einen Schritt nach links. Danach wird das Symbol b durch
das Symbol x ersetzt und die Bewegung nach links fortgestzt, usw..
Das Eingabewort wird akzeptiert, wenn auf diese Weise alle a´s und alle b´s im Eingabewort ersetzt werden können.
Präzisierung
Zur Präzisierung betrachten wir zunächst das folgende Zustandsdiagramm, das eine sogenannten Turingmaschine festlegt.
Die Turingmaschine hat eine nichtleere endliche Menge Z von Zuständen. Im vorliegenden Fall ist das die Menge
Z = {q0, q1, q2, q3, q4}. Der Zustand q0 ist hier als Anfangszustand ausgezeichnet,
der Zustand q4 als ein Endzustand.
Eine Verarbeitung wird durch einen Zustandsübergang (von einem Zustand in einen anderen, gegebenenfalls denselben Zustand) beschrieben. Ein Zustandsübergang erfolgt nur in Abhängigkeit vom gelesenen Symbol. Ein Zustandsübergang beschreibt zusätzlich, wie das das gelesene Symbol überschrieben wird (ggf. durch dasselbe Symbol) und wie sich anschließend der Lese-/Schreibkopf bewegt. R steht für einen Schritt nach rechts, L für einen Schritt nach links und S für keine Bewegung. Letzteres benutzen wir nur für Übergänge in Endzustände. Im Zustandsdiagramm werden diese Informationstripel in der Gestalt (gelesenes Symbol; geschriebenes Symbol, Bewegung) an die Übergangspfeile geschrieben. Die Bedeutung dieser Informationstripel soll anhand konkreter Beispiele weiter erläutert werden.
Das Tripel a;x,R bedeutet: Wenn das Symbol a gelesen wird, dann überschreibe es
mit dem Symbol x und bewege den Lese-/Schreibkopf eine Zelle nach rechts.
Das Tripel a;a,R bedeutet: Wenn das Symbol a gelesen wird, dann überschreibe es
mit dem Symbol a und bewege den Lese-/Schreibkopf eine Zelle nach rechts. Hier wird also das Symbol in der
Zelle nicht verändert.
Das Tripel ∅;∅,L bedeutet: Wenn das Symbol ∅ gelesen wird
(d.h. wenn die Zelle leer ist), dann überschreibe es
mit dem Symbol ∅ und bewege den Lese-/Schreibkopf eine Zelle nach links.
Beachte, dass die Turingmaschine Hilfssymbole benutzen kann, die nicht im Alphabet der zu erkennenden Sprache vokommen. Im vorliegenden Fall ist es das Hilfsssymbol x.
Zusammenfassend lässt sich das Verarbeitungsmodell Turingmaschine
wie folgt charakterisieren.
Eine (deterministische) Turingmaschine ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:
- eine nichtleere, endliche Menge von Zuständen
- eine nichtleere, endliche Menge von Eingabesymbolen,
die das Symbol
∅nicht enthält - eine nichtleere, endliche Menge von Bandsymbolen,
die alle Eingabesymbole und auch das Symbol
∅für eine leere Zelle enthält - eine Überführungsfunktion, die dem aktuellem Zustand in Abhängigkeit von einem gelesenen Symbol den Folgezustand zuordnet, zudem das zu schreibende Symbol und die Bewegung des Lese-/Schreibkopfes
- einen ausgezeichneten Zustand - den Anfangszustand -
- eine Menge von Endzuständen
Bei einer nichtdeterministischen Turingmaschine müssen die Zustandsübergänge nicht eindeutig sein.
Eine Turingmaschine ist also eine Verarbeitungseinheit, die Symbole verarbeitet, sich dabei stets in einem bestimmten Zustand befindet und die zum Zwischenspeichern von Symbolen ein unbegrenztes, beschreibbares und nach rechts und links begehbares Band benutzt.
Spracherkennung mit einer Turingmaschine
Die Menge der Eingabesymbole einer Turingmaschine kann als Alphabet einer Sprache aufgefasst werden.
Unter der Sprache einer Turingmaschine versteht man die Menge aller Wörter aus Eingabesymbolen, die die Turingmaschine vom Anfangszustand in einen Endzustand überführen.
Wenn T eine gegebene Turingmaschine ist,
dann schreiben wir L(T) für die Sprache der Turingmaschine T.