Theoretische Informatik

Chomsky-Hierarchie der Automatentypen

 aufwärts

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

Typ-i-Automaten

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

Typ 0

Ein Typ-0-Automat ist eine nicht­deterministische Zwei-Band-Turing­maschine mit einem Eingabeband und einem einseitig unbe­schränkten Arbeitsband. Auf dem Eingabeband steht das Eingabewort. Die Turing­maschine 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 Begrenzungs­zeichen $ hinaus. Das Begrenzungs­zeichen darf sie nicht durch ein anderes Zeichen über­schreiben.

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

Bild 1: Typ-0-Automat mit Eingabeband und Arbeitsband
Bild 1: Typ-0-Automat mit Eingabeband und Arbeitsband

 

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 vereinigt {Leerzeichen},
A das Arbeits­alphabet,  wobei E' enthalten in A,
d die Übergangs­relation mit  d enthalten in Z × E'? × A × A' × Z,
 hierbei ist A' = A vereinigt {L, R}  sowie  E'? = E' vereinigt {ε},
q Element Z    der Startzustand,
F enthalten in Z    die Menge der Endzustände.

Das Leerzeichen Leerzeichen steht für ein leeres Feld auf dem Eingabe- bzw. dem Arbeitsband; es kommt nicht im Eingabe­alphabet vor. Das Arbeits­alphabet enthält ferner das Band­begrenzungs­zeichen $; dieses kommt ebenfalls nicht im Eingabe­alphabet vor. Die Zeichen L und R bedeuten eine Links- bzw. eine Rechts­bewegung des Schreib-/Lesekopfes auf dem Arbeitsband; diese Zeichen kommen nicht im Arbeits­alphabet vor.

Ein Tupel (s, a, h, h', s') der Übergangs­relation 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. Rechts­bewegung des Schreib-/Lesekopfes auf dem Arbeitsband aus. Nach dem Lesen eines Zeichens a auf dem Eingabeband führt der Automat eine Rechts­bewegung des Lesekopfes auf dem Eingabeband aus, nicht jedoch wenn a = ε ist.

Zu Beginn steht der Lesekopf auf dem ersten Feld des Eingabe­bandes und der Schreib-/Lesekopf auf dem Feld neben dem Band­begrenzungs­zeichen des Arbeits­bandes.

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 = { anbncn  |  n Element natürliche Zahlen }.

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

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Arbeitsband

$
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sehh's'
 0 a a1
 1 εaR0
 0 b L2
 2 εax3
 3 bxL2
 3 cxL4
 4 ε$R5
 5 εxR6
 6 cxR6
 6   L7*


Bemerkung:  Zwei-Band-Turing­maschinen und normale Turing­maschinen sind äquivalente Maschinen­modelle. Zwei-Band-Turing­maschinen lassen sich durch normale Turing­maschinen simulieren und umgekehrt.

Typ 1

Definition:  Ein Typ-1-Automat ist ein Typ-0-Automat, dessen Übergangs­relation wie folgt einge­schränkt ist:

Jeder Zustands­übergang, der das Leerzeichen Leerzeichen auf dem Arbeitsband vorfindet, überschreibt dieses durch ein Zeichen und liest gleichzeitig ein Eingabe­zeichen ein oder aber führt eine Links­bewegung aus.

Ein Typ-1-Automat darf also ein Leerzeichen auf dem Arbeitsband nur dann über­schreiben, wenn er gleichzeitig ein Eingabe­zeichen liest. Eine Rechts­bewegung 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 Arbeits­bandes benutzt wie Eingabe­zeichen auf dem Eingabeband stehen. Ein Typ-1-Automat benutzt also nur einen durch die Länge der Eingabe beschränkten Teil des Arbeits­bandes.

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

Beispiel:  Der Typ-0-Automat aus dem vorigen Beispiel ist ein Typ-1-Automat.

Bemerkung:  Typ-1-Automaten sind äquivalent zu den klassischen linear beschränkten Turing­maschinen.

Typ 2

Ein Typ-2-Automat benutzt sein Arbeitsband in noch weiter einge­schrä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ück­sichtigt werden.

Definition:  Ein Typ-2-Automat ist ein Typ-1-Automat, dessen Übergangs­relation wie folgt einge­schränkt ist:

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 = { anbn  |  n Element natürliche Zahlen }.

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

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Arbeitsband

$
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sehh's'
 0 a a1
 1 εaR0
 0 b L2
 2 εa 3
 3 b L2
 3   L4
 4 ε$R5*





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

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

Bemerkung:  Offenbar ist ein Typ-2-Automat äquivalent zu einem klassischen Stack­automaten, allerdings mit beschränkter Länge des Stacks. Für die Erkennung von Sprachen ist diese Beschränkung aber ohne Belang.

Ein Über­schreiben eines Leerzeichens auf dem Arbeitsband mit anschließender Rechts­bewegung entspricht der push-Operation des Stack­automaten, eine Links­bewegung mit anschließendem Über­schreiben eines Zeichens durch das Leerzeichen entspricht der pop-Operation. Eine Links­bewegung mit anschließender Rechts­bewegung entspricht einer pop-Operation, in der ein Zeichen vom Stack entfernt wird, gefolgt von einer push-Operation, in der dasselbe Zeichen wieder auf dem Stack abgelegt wird.

Typ 3

Definition:  Ein Typ-3-Automat ist ein Typ-2-Automat, bei dem alle Zustands­übergänge von der Form (s, a, Leerzeichen, Leerzeichen, s') sind.

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 nicht­deterministische 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, Leerzeichen, $},  q = 0,  F = {3};  die Übergangs­relation d ist

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Arbeitsband

$
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sehh's'
 0 a  1
 0 a  2
 1 a  1
 1 b  1
 1 a  2
 2    3*






Bemerkung:  Offenbar ist ein Typ-3-Automat dasselbe wie ein klassischer endlicher Automat mit Epsilon-Übergängen, mit dem Unterschied, dass der Typ-3-Automat erst dann in den Endzustand übergeht, wenn er zum Schluss noch ein Leerzeichen auf dem Eingabeband liest und dadurch feststellt, dass er das Eingabewort vollständig gelesen hat.

Aufgaben

Aufgabe 1:  Entwerfen Sie einen Typ-1-Automaten, der die Sprache L = { a2n  |  n Element natürliche Zahlen0 } über dem Alphabet A = {a} erkennt.

Eingabeband

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Arbeitsband

$
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

sehh's'
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       

       

Zusammenfassung

Wir haben den Typ-0-Automaten als nicht­deterministische Zwei-Band-Turing­maschine mit Eingabeband und Arbeitsband eingeführt. Indem die Möglich­keiten, das Arbeitsband zu benutzen, immer weiter einge­schrä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öglich­keiten, 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 Turing­maschinen, bezeichnet als String-Turing­maschinen, charakterisieren. Hier ergeben sich die entsprechenden Typ-i-String-Turing­maschinen durch sehr viel natürlichere Beschränkungen.

 

Weiter mit:   [String-Turingmaschinen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 27.08.2010   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik