Datenverarbeitende Systeme
Kapitel 6: Touring-Automaten und kontextsensitive Sprachen

6.1 Kontextsensitive Sprachen – Typ 1-Grammatiken

Als letztes betrachten wir Sprachen, die nicht einmal kontextfrei sind. Wir haben im Moment keine Methode zur Hand, um eine Sprache in Typ 1 oder Typ 0 einzuordnen. Wir können nur mit dem Pumpig-Theorem aussagen, dass L eben nicht Typ 2 ist und damit 1 oder 0 sein muss. Wir können aber wieder einen Automaten angeben, der eine Sprache von beiden Typen erkennt. Später können wir diesen Automaten so klassifizieren, dass er nur Sprachen vom Typ 1 erkennt (siehe linear beschränkte Automaten) . Zunächst möchte ich aber allgemein den entsprechenden Automat vorstellen:

6.2 Der Touring-Automat

Ein Touring-Automat kommt mit einem einzigen Band aus, auf dem er die Eingabe erhält und auch die Ausgabe erledigt. Das Band dient zusätzlich als Zwischenspeicher. Das Band ist unendlich lang und alle unbeschriebenen Stellen enthalten zunächst Platzhalter (#). Die Ausgabe ist entweder ein Ausgabesymbol oder ein Steuerzeichen, um den Schreib-Lesekopf um eine Position nach links oder rechts zu verschieben.

TA = (X, B, S, s₀, d, s_f ):

X: Eingabealphabet
B: Bandalphabet, X ist Teilmenge von B, # ist aus X, # heißt Leerzeichen
S: endliche Zustandsmenge
s₀: Startzustand
d: Zustandsübergangsfunktion
s_f: Haltezustand

Zu Beginn steht der Schreib-Lesekopf über dem obersten Symbol der Eingabe. Der Automat terminiert, wenn s_f erreicht wurde oder es keine Kante mehr für das Symbol gibt, das sich im aktuellen Zustand gerade unter dem Bandkopf steht. Die Steuerzeichen L und R sind Element von B und bewegen den Kopf nach links oder rechts. Kanten beschriften wir mit a/b, wobei a das Eingabesymbol und b das Ausgabesymbol ist. Ich will wieder auf unser beliebtes Sprachmodell L={ aⁿbⁿcⁿ | n>0} zurückgreifen (wir haben es schon fast vermisst). Entwickeln wir zunächst einen Lösungsansatz:

Lösche das erste a (überschreibe es mit #)
gehe zum letzten b (zum ersten c und eins zurück, read-ahead nicht möglich)
überschreibe dieses b durch ein c (jetzt haben wir ein a und ein b weniger, ein c mehr)
gehe zum letzten c (ans Bandende und eins zurück, siehe 2)
lösche dieses c mit # (das c aus 3 ist jetzt wieder entfernt)
gehe um eins nach links und lösche auch dieses c
gehe um eins nach links
haben wir ein # erreicht, ist das Band leer und das Wort erkannt!
Ansonsten gehe an den Bandanfang und um eins nach rechts auf das vorderste a
wiederhole 1 – 9 solange, bis in 8 terminiert werden kann

Wir gewinnen folgenden Automaten:

Man könnte diesen Automaten noch optimieren, indem man S3 und S4 zusammenfasst.

6.3 Touringberechenbare Funktionen

Eine Funktion gilt als von einem Touring-Automat berechenbar, wenn es einen TA gibt, der genau dann für ein eingegebenes Wort w aus X* terminiert, wenn w im Definitionsbereich der Funktion liegt. Dann steht nach der Terminierung der Funktionswert f(w) auf dem Band.

Ein Touring-Automat ist durch eine Programmiersprache simulierbar, wenn wir einen Speicher finden, der nach beiden Seiten hin offen ist (Touring-Band). Dazu splitten wir das Band in zwei Hälften, einen Teil links vom Bandkopf und einen Teil rechts davon. Das Zeichen unter dem Bandkopf steht im rechten Speicher. Als Speicher legen wir zwei Stacks an und nennen sie LS (left Stack) und RS (right Stack). Eine Linksbewegung des Kopfes schiebt das oberste Zeichen von RS in LS, eine Rechtsbewegung macht das umgekehrte. Wenn wir ein Zeichen überschreiben, löschen wir zunächst das oberste Zeichen von RS und schieben das neue Zeichen auf den RS. Um diesen Algorithmus herum legen wir eine Schleife, die Zustandsübergangsfunktionen liegen in einer Tabelle im Speicher. Die Implementierung bleibt jedem selbst überlassen.

Umgekehrt wollen wir versuchen, eine Programmiersprache durch einen TA zu simulieren. Wenn uns das gelingt, können wir in Kombination mit dem obigen Algorithmus eine beliebige Sprache in eine beliebige andere übersetzen, in dem wir einen TA dazwischenbauen. Ob das der einfachste Weg ist, sei dahingestellt.

Um uns das Leben einfach zu machen, zeigen wir erst einmal, das jede Programmiersprache aus einfachen Grundbestandteilen besteht, die Operationen auf ganzen Zahlen n >= 0 erlauben. Schließlich besteht jede Zahl aus eine Folge von Bits, deren Interpretation als Ganzzahl oder Fließkommazahl mit oder ohne Vorzeichen am Ende dem Prozessor überlassen ist (na ja, wir müssen es ihm schon sagen). Alles, was unsere Sprache können muss, ist, eine Variable nullen (x=0), eins addieren (x++) oder eins subtrahieren (x--). Letztlich brauchen wir noch eine while-Schleife. Wir codieren Zahlen auf dem Band in unärer Darstellung. Null entspricht einem Strich, eins zwei Strichen und so weiter. Wollen wir eine Funktion mit mehreren Variablen realisieren (Vektoren, Schleifen, etc. ), so trennen wir die Variablen auf dem Band mit einem $-Zeichen. Die Implementierung der einzelnen Automaten überlasse ich dem geneigten Leser ebenso, wie den Aufbau von komplexeren Funktionen wie Summen oder if-then-else-Verzweigungen.

Damit ist gezeigt: Programmiersprachen sind von Touring-Automaten berechenbar und umgekehrt. Sprachen, die von Touring-Automaten akzeptiert werden heißen Regelsprachen.

6.3.1 Das Problem mit der Terminierung

Wir kennen drei Möglichkeiten der Arbeitsweise eines Touring-Automaten: Er kann in einem Haltezustand enden, irgendwann abbrechen, wenn es keine Kante für die aktuelle Eingabe gibt oder seine Arbeit bis in alle Ewigkeit fortsetzten ohne zu terminieren. Dabei haben wir das Problem, dass wir nie sagen können, ob der Automat nicht doch 5 Sekunden vor der Ewigkeit terminiert oder nicht. Nur weil eine Funktion nach 10 Millionen Jahren noch nicht fertigberechnet ist, heißt das noch nicht, das sie nie berechnet werden kann. Denken wir an die Faktorisierung langer Primzahlen oder die Zerlegung eines menschlichen Körpers in seine Einzelbestandteile wie es beim beamen a la Star-Trek nötig wäre.

Folgende Tabelle soll Aufschluss geben, wie ein Automat reagiert, der L(TA) erkennt (2 Fälle: L nichtverkürzend oder L rekursiv - siehe unten) oder Funktionen berechnet:

		TA erkennt L(TA)	TA berechnet Funktion	TA erkennt L(rekursiv)
TA terminiert	erreicht Haltezustand	Eingabe lag in der Sprache	Eingabe lag in der Sprache, f(w) steht auf dem Band	Eingabe lag in der Sprache
	bricht ab	Eingabe lag nicht in der Sprache	Kommt nicht vor	Eingabe lag nicht in der Sprache
TA terminiert nicht		Eingabe lag nicht in der Sprache	Eingabe lag nicht in der Sprache	Kommt nicht vor

Eine Sprache heißt rekursiv, wenn es einen Automaten gibt, der für jedes Eingabewort x terminiert. Ein solcher Automat heißt terminierend.

6.3.2 Linear beschränkte Automaten

Ein Automat heißt linear beschränkt, wenn er mit einem endlichen Band auskommt. Solche Automaten sind in der Praxis von Bedeutung, da Computer im allgemeinen nur über endlich viel Speicher verfügen. Das Band dieser Automaten ist links und rechts jeweils durch zwei unterschiedliche Steuerzeichen begrenzt, die nicht überfahren und auch nicht überschrieben werden können. Linear beschränkte Automaten akzeptieren Sprachen, die mindestens vom Typ 1 sind. Damit haben wir eine Möglichkeit nachzuweisen, dass eine Sprache genau Typ 1 ist: Zeige mit Pumping-Theorem, dass L nicht Typ 2 und gib einen linear beschränkten Touring-Automaten dazu an.