Theoretische Informatik

Der Chomsky-Hierarchie der Grammatiktypen entspricht eine Hierarchie der Automatentypen. Dies sind die Automatentypen Turingmaschine, linear beschränkte Turingmaschine, Stackautomat und endlicher Automat. Ziel ist es hier, diese Automatentypen als echte Spezialfälle voneinander darzustellen. Dazu ist es erforderlich, die entsprechenden Automatentypen ein wenig zu modifizieren. Denn ein Stackautomat mit seinen zwei Bändern, dem Eingabeband und dem Stack, kann kein Spezialfall einer Ein-Band-Turingmaschine sein. Die Hierarchie beginnt daher mit einer speziellen Zwei-Band-Turingmaschine.

Typ-i-Automaten

Wir bezeichnen die entsprechend modifizierten Automatentypen als Typ-i-Automaten. Die Modifikationen sind notwendig, damit eine echte Hierarchie von Spezialfällen zustande kommt.

Typ 0

Ein Typ-0-Automat ist eine nichtdeterministische Zwei-Band-Turingmaschine mit einem Eingabeband und einem einseitig unbeschränkten Arbeitsband. Auf dem Eingabeband steht das Eingabewort. Die Turingmaschine kann auf dem Eingabeband nur von links nach rechts lesen. Auf dem Arbeitsband kann sie lesen und schreiben und sich beliebig nach links und rechts bewegen, jedoch nicht über das linke Begrenzungszeichen $ hinaus. Das Begrenzungszeichen darf sie nicht durch ein anderes Zeichen überschreiben.

Das folgende Bild 1 zeigt schematisch einen Typ-0-Automaten mit Eingabewort x = x₀ ... x₅ auf dem Eingabeband.

Formal ist ein Typ-0-Automat wie folgt definiert:

Definition:  Ein Typ-0-Automat ist ein Tupel

M = (Z, E, A, d, q, F).

Hierbei ist

Z		eine endliche, nichtleere Menge von Zuständen des Steuerwerks,
E		das Eingabe­alphabet,  ferner E'  =  E ∪ {},
A		das Arbeits­alphabet,  wobei E' ⊆ A,
d		die Übergangs­relation mit  d ⊆ Z × E'? × A × A' × Z,
		hierbei ist A' = A ∪ {L, R}  sowie  E'? = E' ∪ {ε},
q ∈ Z		der Startzustand,
F ⊆ Z		die Menge der Endzustände.

Das Leerzeichen steht für ein leeres Feld auf dem Eingabe- bzw. dem Arbeitsband; es kommt nicht im Eingabealphabet vor. Das Arbeitsalphabet enthält ferner das Bandbegrenzungszeichen $; dieses kommt ebenfalls nicht im Eingabealphabet vor. Die Zeichen L und R bedeuten eine Links- bzw. eine Rechtsbewegung des Schreib-/Lesekopfes auf dem Arbeitsband; diese Zeichen kommen nicht im Arbeitsalphabet vor.

Ein Tupel (s, a, h, h', s') der Übergangsrelation bewirkt folgende Aktion des Automaten: Wenn sich der Automat im Zustand s befindet und das Zeichen a auf dem Eingabeband und das Zeichen h auf dem Arbeitsband liest, so schreibt er das Zeichen h' auf das Arbeitsband und geht in den Zustand s' über. Wenn allerdings h' eines der Zeichen L oder R ist, so schreibt der Automat kein Zeichen, sondern führt stattdessen eine Links- bzw. Rechtsbewegung des Schreib-/Lesekopfes auf dem Arbeitsband aus. Nach dem Lesen eines Zeichens a auf dem Eingabeband führt der Automat eine Rechtsbewegung des Lesekopfes auf dem Eingabeband aus, nicht jedoch wenn a = ε ist.

Zu Beginn steht der Lesekopf auf dem ersten Feld des Eingabebandes und der Schreib-/Lesekopf auf dem Feld neben dem Bandbegrenzungszeichen des Arbeitsbandes.

Der Automat hält, wenn er keinen Zustandsübergang mehr ausführen kann. Der Automat erkennt das Wort auf dem Eingabeband, wenn er hält und sich dabei in einem Endzustand befindet.

Beispiel:  Der folgende Typ-0-Automat M = (Z, E, A, d, q, F) erkennt die Sprache L = { aⁿbⁿcⁿ  |  n ∈ ℕ }.

Es ist Z = {0, ..., 7},  E = {a, b, c},  A = {a, b, c, x, , $},  q = 0,  F = {7};  die Übergangsrelation d ist

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

Arbeitsband

$

 

 

 

 

 

 

 

 

 

 

 

 

Eingabewort

   

 

s	e	h	h'	s'
0	a		a	1
1	ε	a	R	0
0	b		L	2
2	ε	a	x	3
3	b	x	L	2
3	c	x	L	4
4	ε	$	R	5
5	ε	x	R	6
6	c	x	R	6
6			L	7*

Typ 1

Ein Typ-1-Automat darf also ein Leerzeichen auf dem Arbeitsband nur dann überschreiben, wenn er gleichzeitig ein Eingabezeichen liest. Eine Rechtsbewegung darf er bei einem Leerzeichen auf dem Arbeitsband gar nicht ausführen.

Erreicht wird hierdurch, dass der Typ-1-Automat höchstens so viele Felder des Arbeitsbandes benutzt wie Eingabezeichen auf dem Eingabeband stehen. Ein Typ-1-Automat benutzt also nur einen durch die Länge der Eingabe beschränkten Teil des Arbeitsbandes.

Bei einem Typ-1-Automaten sind also Zustandsübergänge der Form (s, ε, , x, s') mit x ∈ A verboten. Erlaubt ist dagegen (s, a, , x, s') mit a ∈ E', x ∈ A, ebenso (s, ε, , L, s').

Typ 2

Ein Typ-2-Automat benutzt sein Arbeitsband in noch weiter eingeschränkter Weise, nämlich wie einen Stack. Ob ein Automat vom Typ 2 ist, lässt sich nicht an den einzelnen Zustandsübergängen ablesen, sondern nur indem zu gewissen Zustandsübergängen auch die möglichen Folge-Zustandsübergänge berücksichtigt werden.

Ein Typ-2-Automat ist ein Spezialfall eines Typ-1-Automaten.

Beispiel:  Folgender Automat M = (Z, E, A, d, q, F) erkennt die Sprache L = { aⁿbⁿ  |  n ∈ ℕ }.

Es ist Z = {0, ..., 5},  E = {a, b},  A = {a, b, , $},  q = 0,  F = {5};  die Übergangsrelation d ist

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

Arbeitsband

$

 

 

 

 

 

 

 

 

 

 

 

 

Eingabewort

   

 

s	e	h	h'	s'
0	a		a	1
1	ε	a	R	0
0	b		L	2
2	ε	a		3
3	b		L	2
3			L	4
4	ε	$	R	5*

Anhand der Übergangsrelation ist ersichtlich, dass es sich hier um einen Typ-2-Automaten handelt. Beispielsweise wird durch den Zustandsübergang (1, a, , a, 2) ein Leerzeichen auf dem Arbeitsband überschrieben. Daher müssen alle Folge-Zustandsübergänge eine Rechtsbewegung ausführen. Der einzige Folge-Zustandsübergang, der vom Zustand 2 ausgeht, führt tatsächlich eine Rechtsbewegung aus.

In ähnlicher Weise lässt sich überprüfen, dass die Bedingung für Linksbewegungen hier ebenfalls erfüllt ist.

Typ 3

Ein Typ-3-Automat benutzt sein Arbeitsband überhaupt nicht, sondern liest nur auf dem Eingabeband und vollführt dabei Zustandsübergänge.

Ein Typ-3-Automat ist ein Spezialfall eines Typ-2-Automaten.

Beispiel:  Der folgende nichtdeterministische Typ-3-Automat M = (Z, E, A, d, q, F) erkennt die Sprache L  =  a | a(a|b)*a.

Es ist Z = {0, ..., 3},  E = {a, b},  A = {a, b, , $},  q = 0,  F = {3};  die Übergangsrelation d ist

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

Arbeitsband

$

 

 

 

 

 

 

 

 

 

 

 

 

Eingabewort

   

 

s	e	h	h'	s'
0	a			1
0	a			2
1	a			1
1	b			1
1	a			2
2				3*

Aufgaben

Aufgabe 1:  Entwerfen Sie einen Typ-1-Automaten, der die Sprache L = { a²ⁿ  |  n ∈ ℕ₀ } über dem Alphabet A = {a} erkennt.

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

Arbeitsband

$

 

 

 

 

 

 

 

 

 

 

 

 

Eingabewort

   

 

s	e	h	h'	s'

       

Zusammenfassung

Wir haben den Typ-0-Automaten als nichtdeterministische Zwei-Band-Turingmaschine mit Eingabeband und Arbeitsband eingeführt. Indem die Möglichkeiten, das Arbeitsband zu benutzen, immer weiter eingeschränkt werden, ergeben sich Typ-1-, Typ-2- und Typ-3-Automaten. Ein Typ-3-Automat benutzt sein Arbeitsband überhaupt nicht mehr. Etwas künstlich erscheint allerdings die Beschränkung der Möglichkeiten, das Arbeitsband zu benutzen, beim Typ-2-Automaten.

Es stellt sich heraus, dass diese Beschränkungen gerade so gefasst sind, dass die entsprechenden Typ-i-Automaten genau die Typ-i-Sprachen der Chomsky-Hierarchie erkennen.

Die Chomsky-Hierarchie lässt sich auch durch eine andere spezielle Art von Turingmaschinen, bezeichnet als String-Turingmaschinen, charakterisieren. Hier ergeben sich die entsprechenden Typ-i-String-Turingmaschinen durch sehr viel natürlichere Beschränkungen.