3.3 Linear-beschränkte Automaten und kontextabhängige Klassen

Die Monotonie der Typ-1 Grammatiken erlaubt es, das Speicherband des akzeptierenden Turing-Automaten auf den Bereich des gegebenen Eingabewortes linear zu beschränken.

Definition: Linear beschränkter Automat Eine Struktur B = (X, Y, Z, h, z0, F, [, ] ) heißt linear-beschränkter Automat, wenn (X, Y, Z, h, z0, F) ein (nichtdeterministischer) Turing-Automat (ohne Blank), [ , ] Y \ ( X Z ) (linke bzw. rechte Randmarke) und aus (y´, z´, o) h (y, z) folgt y´ = [ bzw. ] genau dann, wenn y = [ bzw. ] und aus y = [ bzw ] folgt o l bzw. r . (Die Randmarken dürfen weder geschrieben, verändert, noch überschritten werden.

Durch L (B) = { p p X* und [z₀p] * [uz_fv] mit z_f F } wird die von B akzeptierte Sprache bezeichnet.

Der Automat B kann nur auf dem durch das Eingabewort beschriebenen Bandbereich arbeiten. Die Arbeitsweise von B wird durch das folgende Bild verdeutlicht:

Satz: Typ-1 Sprachen und linear-beschränkte Automaten Eine Sprache L ist genau dann vom Typ-1, wenn es einen linear beschränkten Automaten B mit L (B) \ { } = L gibt.

(Das leere Wort kann durch einen Automaten B akzeptiert , durch eine monotone Grammatik aber nicht generiert (erzeugt) werden.)

Beweisskizze:

1. Zu jeder monotonen Grammatik G = ( M, A, R, S ) existiert ein linear-beschränkter Automat B mit L (G) = L (B).

   O.B.d.A. kann G als Kuroda-Normalform vorausgesetzt werden, wobei für die Regeln (u, v) aus R gilt: u = v 2 und u M M² und S nicht in v oder u = S und v = Sy . Für jedes p L (G) gibt es dann eine Ableitung
   S Sq p mit q = p -1 , d.h., es wird zunächst ein mit S beginnendes Wort der Länge von p aufgebaut. (Es ist nur ein Metazeichen m mit q = mp^-1 erforderlich.)

   Man kann nun einen linear-beschränkten Automaten
   B = ( A, Y, Z, h, z₀, F, [, ] ) angeben, wo h die längentreuen Regeln rückwärts ausführt und das eingegebene Wort dann akzeptiert wird, wenn zwischen den Randmarken ein Wort entsteht, daß mit den Regeln (S, v) R aus S ableitbar ist.

   (Man kann auch einen Automaten mit einem zweispurigen Band konstruieren, der auf der zweiten Spur nichtdeterministisch ein Wort aus L(G) erzeugt und dieses dann mit dem auf der ersten Spur stehenden Eingabewort vergleicht. Der Automat akzeptiert, wenn beide Spuren dasselbe Wort enthalten.)

2. Zu jedem linear-beschränkten Automaten B existiert eine monotone Grammatik G mit L (B) \ { } = L (G).
   Die Konstruktion von G wird analog zum entsprechenden Satz für Turing-Automaten durchgeführt, nur ist hier zu beachten, daß störende Hilfszeichen wegen Monotonie nicht gelöscht werden können. Mit den Metazeichen
   z^x, z^[, z^], S, , für x X und z Z werden deshalb folgende Regeln konstruiert:

   Ableitungsanfang:	(S, ), ( , x ), ( , x), ( , z] ) für x X und
   	( ] , zf, r ) h ( ] , z ) , zf F.

   Simulation von B:	( z´x´ , zx )	bei ( x´, z´, o ) h (x, z) ,
   	( x´ z´x´´ , zxx´)	bei ( x´, z´, r ) h (x, z), x´ X,
   	( z´x´´x´, x´zx )	bei ( x´, z´, l ) h (x, z), x´ X und
   	(x´z´] , zx), ( [zx, [ x )	bei (x´, z´, r ) h (x, z), x X.

   Die Grammatik mit den so eingeführten Metazeichen und Regeln ist monoton und generiert die von verschiedenen Wörter aus L (B).

Die linear-beschränkten Automaten charakterisieren demnach gerade die Klasse der Typ-1 Sprachen.

3.4   Sprach- und Automatenklassen

Lf	endliche Sprachen	Le	entscheidbare Sprachen
L3	reguläre Sprachen (Typ-3)	EA DEA	endliche Automaten determ. endliche Automaten
L2d	determ. kontextfreie Sprachen	DKA	determ. Kellerautomaten
L2	kontextfreie Sprachen (Typ-2)	KA	Kellerautomaten
L1	kontextabhänige Sprachen (Typ-1)	LBA	linear-beschränkte Automaten
L0	aufzählbare Sprachen (Typ-0)	TA DTA HTA	Turing-Automaten determ. Turing-Automaten haltender Turing-Automat