Eine String-Turingmaschine arbeitet ähnlich wie die klassische Turingmaschine. Statt des Arbeitsbandes verwendet sie jedoch einen Arbeitsstring, in dem sie auch Zeichen einfügen und löschen kann. Links- und Rechtsbewegungen sowie Einfüge- und Lösch-Aktionen der String-Turingmaschine werden als Cursor-Aktionen bezeichnet.
Wir verwenden String-Turingmaschinen zur Erkennung von Sprachen. Indem die zulässigen Cursor-Aktionen der String-Turingmaschine geeignet eingeschränkt werden, lassen sich genau die Sprachklassen der Chomsky-Hierarchie erkennen. Es ergibt sich so eine Chomsky-Hierarchie der String-Turingmaschinen (Bild 1).
| Sprachklasse | Cursor-Aktionen |
|---|---|
| Typ 0 | I, L, R, D |
| Typ 1 | L, R, D |
| Typ 2 | R, D |
| Typ 3 | D |
Bild 1: Zulässige Cursor-Aktionen von String-Turingmaschinen
Die Cursor-Aktionen, die der String-Turingmaschine grundsätzlich zur Verfügung stehen, sind Einfügen (I – insert), Rechtsbewegung (R), Linksbewegung (L) und Löschen (D – delete). Im Folgenden werden String-Turingmaschinen angegeben, deren Cursor-Aktionen nach und nach eingeschränkt werden; diese werden als Typ-i-String-Turingmaschinen bezeichnet, und es wird der Zusammenhang mit den Typ-i-Sprachen und den klassischen Automatentypen Turingmaschine, Stackautomat und endlicher Automat hergestellt.
Die Typ-0-Sprachen werden genau von den klassischen Turingmaschinen erkannt. Eine String-Turingmaschine ohne Einschränkungen der Menge der möglichen Cursor-Aktionen { I, R, L, D } ist äquivalent zur klassischen Turingmaschine. Wie diese erkennt sie genau die Typ-0-Sprachen und wird daher als Typ-0-String-Turingmaschine bezeichnet.
Definition: Eine String-Turingmaschine ist vom Typ 0, wenn für die Übergangsrelation d gilt
d ⊆ Z × A × A0 × Z mit A0 = A ∪ { I, R, L, D }
Die Äquivalenz von klassischer Standard-Turingmaschine und String-Turingmaschine lässt sich dadurch zeigen, dass sich Maschinen der einen Art durch Maschinen der anderen Art simulieren lassen und umgekehrt.
Die String-Turingmaschine kann eine Standard-Turingmaschine simulieren. Hierzu führt sie alle Aktionen der Standard-Turingmaschine genauso aus, nur wenn sie nach einer Rechtsbewegung auf die Endemarkierung & trifft, geht sie um ein Feld nach links und führt eine Einfüge-Aktion aus. Dadurch kann die String-Turingmaschine das Arbeitsband nach rechts so weit ausdehnen, wie es erforderlich ist.
Umgekehrt kann eine Standard-Turingmaschine die String-Turingmaschine simulieren. Eine Einfüge-Aktion führt sie dadurch aus, dass sie alle Zeichen, die auf dem Arbeitsband rechts von der Einfügeposition stehen, um ein Feld nach rechts verschiebt. Eine Lösch-Aktion führt sie dadurch aus, dass sie alle Zeichen, die auf dem Arbeitsband rechts von der Löschposition stehen, um ein Feld nach links verschiebt und danach ein Feld nach links geht.
Die Typ-1-Sprachen oder kontextsensitiven Sprachen werden genau von den nichtdeterministischen linear beschränkten Turingmaschinen erkannt. Eine Turingmaschine ist linear beschränkt, wenn sie den Bereich des Arbeitsbandes, auf dem das Eingabewort steht, nicht verlässt. Für eine String-Turingmaschine ergibt sich diese Beschränkung, wenn die Übergangsrelation d keine Einfüge-Aktion zulässt.
Definition: Eine String-Turingmaschine ist vom Typ 1, wenn für die Übergangsrelation d gilt
d ⊆ Z × A × A1 × Z mit A1 = A ∪ { R, L, D }
Die Typ-2-Sprachen oder kontextfreien Sprachen werden genau von den nichtdeterministischen Stackautomaten erkannt. Eine String-Turingmaschine, deren Übergangsrelation d keine Einfüge-Aktionen und keine Linksbewegungen zulässt, sondern nur Rechtsbewegungen und Lösch-Aktionen, verhält sich ähnlich wie ein Stackautomat. Der Stack wird durch linken Teil des Arbeitsstrings bis zur Cursor-Position dargestellt. Ein Zugriff auf diesen Teil ist nur durch eine Lösch-Aktion, also durch Lesen und anschließendes Löschen des Zeichens an der Cursor-Position möglich; dies entspricht der pop-Operation beim Stack. Eine push-Operation ergibt sich dadurch, dass ein Zeichen des Arbeitsstrings gelesen und durch ein Stack-Zeichen überschrieben wird.
Definition: Eine String-Turingmaschine ist vom Typ 2, wenn für die Übergangsrelation d gilt
d ⊆ Z × A × A2 × Z mit A2 = A ∪ { R, D }
Der Beweis, dass die nichtdeterministischen Typ-2-String-Turingmaschinen genau die Typ-2-Sprachen erkennen, findet sich unter Typ-2-String-Turingmaschine.
Die Typ-3-Sprachen oder regulären Sprachen werden von den endlichen Automaten erkannt. Ein endlicher Automat lässt sich durch eine String-Turingmaschine nachbilden, deren Übergangsrelation d keine Einfüge-Aktionen, keine Links- und keine Rechtsbewegungen, sondern nur Lösch-Aktionen zulässt.
Definition: Eine String-Turingmaschine ist vom Typ 3, wenn für die Übergangsrelation d gilt
d ⊆ Z × A × A3 × Z mit A3 = { D }
Da der Cursor nach einer Lösch-Aktion auf das vorhergehende Zeichen zeigt, wird das Eingabewort in diesem Fall von rechts nach links abgearbeitet. Zu Beginn zeigt der Cursor auf das rechte Begrenzungszeichen &. Die Typ-3-String-Turingmaschine erkennt somit das Spiegelbild derjenigen regulären Sprache, die ein endlicher Automat bei Abarbeitung von links nach rechts erkennt. Das Spiegelbild einer regulären Sprache ist aber regulär.
Mit folgenden Simulationen lässt sich die Arbeitsweise bestimmter String-Turingmaschinen veranschaulichen.
Die folgende String-Turingmaschine erkennt die Sprache L = { anbncn | n ∈ ℕ }. Die Maschine löscht das erste a, geht über weitere a's weiter nach rechts, löscht das erste b, geht über weitere b's weiter nach rechts, löscht das erste c, und geht über weitere c's bis zum rechten Begrenzungszeichen &. Danach geht sie wieder an den Anfang und beginnt von vorne.
Die folgende String-Turingmaschine erkennt die Sprache L = a | a(a|b)*a. Da es sich um eine Typ-3-String-Turingmaschine handelt, zeigt der Cursor zu Beginn auf das rechte Begrenzungszeichen &.
Aufgabe 1: Entwerfen Sie eine nichtdeterministische Typ-2-String-Turingmaschine zur Erkennung der Sprache L = { wwR | w ∈ {a, b}+, wR ist das Spiegelbild von w }.
| s | a | a' | s' |
|---|---|---|---|
| 0 | $ | R | 0 |
Aufgabe 2: Entwerfen Sie eine deterministische Typ-1-String-Turingmaschine zur Erkennung der Sprache L = { a2n | n ∈ ℕ0 } über dem Alphabet A = {a}.
| s | a | a' | s' |
|---|---|---|---|
| 0 | $ | R | 0 |
[Lan 10] H.W. Lang: A Characterization of the Chomsky Hierarchy by String Turing Machines. In: H.R. Arabnia, G.A. Gravvanis, A.M.G. Solo (Hrsg.): Proceedings of the 2010 International Conference on Foundations of Computer Science, CSREA Press, 109-114 (2010)
Weiter mit: [up]