3.1 Kellerautomaten und kontextfreie Sprachen

Zur Beschreibung formaler Sprachen wurden bisher Regelsysteme verwendet, die formale Sprachen als Wortmengen erzeugen (generieren). Wir betrachten jetzt Verfahren, mit denen entschieden werden kann, ob ein gegebenes Wort zu einer bestimmten Sprache gehört. Wir sprechen dann im Gegensatz zur Regelgrammatik, die die Sprache generiert, von einer akzeptiven Grammatik bzw. von einem Akzeptor. Wie schon bei endlichen Automaten im Zusammenhang mit regulären Sprachen geben wir das Verfahren als abstrakte Maschine an.
Dazu erweitern wir zunächst den Begiff des endlichen Automaten, indem wir neben dem Eingabespeicher (ROM) einen Lese-Schreib-Speicher (RAM) zur Verfügung stellen, diesen einschränkend aber wie einen Keller benutzen. Dieser Speicher kann wieder Wörter über einem (Keller-) Alphabet aufnehmen und über die Operationen push (Einschreiben in den Keller), pop (Löschen des obersten Kellerelements) und top (Lesen des obersten Kellerelementes) benutzt werden. Wenn p, q Wörter über dem Kelleralphabet Y und y Element von Y, dann gilt für diese Operationen push(p, q) = pq, pop(py) = p und top(py) = y. Dabei steht das oberste Kellerelement am rechten Ende des Kellerwortes, d.h. wir lesen den Keller von rechts nach links. (Natürlich kann das auch umgekehrt festgelegt werden.) Die so festgelegten abstrakten Maschinen (siehe Schema) werden Kellerautomat genannt.

Definition: Kellerautomat Eine Struktur K = ( X, Y, Z, h, z0, S, F ) heißt (endlicher) Kellerautomat, wenn X (Eingabealphabet), Y (Kelleralphabet), Z (Zustandsmenge) nichtleere endliche Mengen, z0  Z (Anfangszustand), S  Y (Startsymbol), F  Z (Endzustandsmenge), h eine Funktion aus ( X  { } )  Z  Y in die Menge aller endlichen Teilmengen von Z  Y*.

Bemerkung: Der Kellerautomat ist allgemein nicht-deterministisch.

Die Elemente der endlichen Mengen h( x, z, y ), wo x das gelesene Zeichen des Eingabebandes oder das leere Wort, z den vorliegenden Zustand und y das oberste Kellersymbol bezeichnet, sind Paare ( z, q ) aus Folgezustand z und zu schreibendem Kellerwort q als mögliche Reaktionen des Automaten. Falls dabei immer nur höchstens eine Reaktion möglich ist, heißt K deterministisch.

Arbeitsweise des Kellerautomat K:

Die momentane Situation von K wird durch eine Konfiguration k = ( p, z, q ) beschrieben, wo p das gegebene Eingabewort (Belegung des Eingabebandes ab aktueller Position), z den aktuellen Automatenzustand und q das vorliegende Kellerwort (Belegung des Kellerbandes) angibt.
Die Konfigurationen ( p, z₀, S ) heißen Anfangskonfigurationen.
Die Konfigurationen (  , z,  ) bzw. ( , z_f, q ) mit z_f F werden als Endkonfigurationen bezeichnet.
Mit Hilfe der Funktion h wird zu jeder Konfiguration k eine Menge von Folgekonfigurationen k´ (in Zeichen: k  k´) wie folgt bestimmt:
(p, z, q)  (p´, z´, q´) genau dann, wenn p=xp´, q=q₁y, q´=q₁q₁´ und (z´, q₁´)  h(x, z, y)
für y  Y , q₁, q₁´  Y* und x  ( X  { } ).
Durch * bezeichnen wir wieder die transitive und reflexive Hülle von  und beschreiben damit Konfigurationsfolgen. Dabei ist k * k´ genau dann, wenn k = k´ oder es gibt eine Folge k₀ ,..., k_n von Konfigurationen mit k₀ = k , k_n = k´ und k_i k_i+1 für alle 0  i < n.

 

Definition: Akzeptierte Sprache Die Wortmenge L (K) = {p  p  X* und es existiert ein z  Z mit ( p, z0, S ) * (  , z,  ) } heißt die vom Kellerautomat K mit leerem Keller akzeptierte Sprache. Die Wortmenge LF(K) = { p  p  X* und ( p, z0, S ) * (  , zf, q ) für ein zf F und q  Y* } heißt die vom Kellerautomat K mit Endzustand akzeptierte Sprache.

Bemerkung: Allgemein ist L ( K )  L_F ( K ). Wie später gezeigt wird, kann man durch

Modifikation des Kellerautomat K den einen in den anderen Fall überführen.

Beispiel: Der Kellerautomat K = ( { 0,1 }, { a,b,c }, ( z₀, z₁ }, h, z₀, a,  ) mit h nach Tabelle

Bemerkung: Kellerautomat können auch wieder durch Graphen beschrieben werden,

wobei den Zuständen die Knoten und den durch h mit (z´, q)  h ( x, z, y ) möglichen Übergängen die mit ( x, y, q ) beschrifteten Kanten entsprechen.

Der Kellerautomat aus dem obigen Beispiel ist durch den folgenden Graphen bestimmt.

Die Übergänge von z nach z´ für ( z´, q )  h (  , y, z ) heißen -Übergänge.

Beweis:

1. L (K) = L_F (K´) :
   (K akzeptiert mit leerem Keller, K´ akzeptiert mit Endzustand)
   Der Kellerautomat K = ( X, Y, Z, h, z₀, S,  ) wird durch den Kellerautomat
   K' = ( X, Y´, Z´, h´, z₀´ , S´, {z } ) simuliert.
   Wir führen ein neues Startsymbol S´ ein und erweitern die Zustandsmenge Z durch Hinzunahme eines Anfangszustandes z₀´ und eines Endzustandes z zu der neuen Zustandsmenge Z´.
   S´  Y, z₀´, z Z, Y´ = Y  {S´}, Z´= Z  { z₀´, z }
   Für alle x  X, y  Y, z  Z ist h' und h identisch. Lediglich für das neue Startsymbol und den Anfangszustand zo´ konstruieren wir h´ derart, daß ausgehend vom Startzustand z₀´ und vom Startsymbol S´ in den Zustand z₀ mit der Kellerinschrift S´S übergegeangen wird. Die neu entstandene Konfiguration ist die Startkonfiguration des Kellerautomat K. Akzeptiert der Automat K mit leerem Keller, so ergibt sich die Kellerinschrift von K' zu S´ . Anschließend wird in den Endzustand z übergegangen.
   h´( , z₀´, S´) = { (z₀, S´S) },
   h´( , z, S´) = { (z ,  ) },
   h´(x, z, y) = h (x, z, y) für alle x  X, y  Y, z  Z .
   Falls K determiniert ist, dann ist auch K´ nach dieser Konstruktion determiniert.
2. L_F (K) = L (K´)
   (K akzeptiert mit Endzustand, K´ akzeptiert mit leerem Keller)
   Der Kelleautomat K = ( X, Y, Z, h, z₀, S, Z_F ) wird durch den Kellerautomat
   K´= ( X, Y´, Z´, z₀´, h´, S´,  ) simuliert.
   Wir konstruieren eine neue Zustandsmenge Z´ durch Hinzunahme der Zustände z₀´,z ´. Das Kelleralphabet Y´ ergibt sich aus dem Kelleralphabet Y, erweitert um ein neues Startsymbol S´.
   S´  Y, z₀´, z ´  Z, Y´= Y  {S´}, Z´= Z  { z₀´, z ´} und
   Die Überführungsfunktion h´ wird so gebildet, daß bei erreichen eines Endzustandes (z  Z_F) in einen neuen Zustand z ´ übergegangen wird, um anschließend den Keller vollständig zu leeren. Insgesamt gilt:
   h´( , z₀´, S´) = { (z₀, S´S) },
   h´( , z ´, y) = { (z ´,  ) } für alle y  Y´,
   h´( , z, y) = { (z ´,  ) } für alle y  Y, z  Z_F ,
   h´(x, z, y) = h (x, z, y) für alle x  X, y  Y, z  Z.

Satz: Kellerautomat und kontextfreie Sprachen Eine Sprache L ist genau dann kontextfrei, wenn es einen Kellerautomat K mit L = L (K) gibt.

 

Beweis:

1. Wenn L kontextfrei, dann gibt es einen Kellerautomat K mit L (K) = L . O.B.d.A. können wir voraussetzen, daß L durch eine Grammatik
   G = (M, A, R, S) in reduzierter Chomsky-Normalform erzeugt wird, d.h.,
   L = L(G).
   Wir bilden den Kellerautomat
   K = (A, (M  A), {z}, h, z, S,  ) mit
   h (x, z, x) = {(z,  )}, h ( , z, u) = {(z, v)} für x  A, u  M und (u, v)  R.

   Man kann zeigen, daß es zu jeder Linksableitung eines Wortes p aus L bzgl. G eine Konfigurationsfolge von K gibt, so daß S  p gdw.
   (p, z, S) * ( , z,  ) .

   Der Kellerautomat simuliert mit den Übergängen ( , u, v) die Linksableitung und schreibt jeweils das Spiegelbild der durch die Regelanwendung erzeugten Wörter als Zwischenergebnisse in den Keller. Die Überführung (x, x,  ) dient dazu, den Keller von Eingabesymbolen aus A zu säubern, die bei der Simulation im Keller entstehen. Genauer wird der Beweis induktiv über die Länge der Ableitung bzw. Konfigurationsfolge geführt.

2. Wenn K ein Kellerautomat, dann ist die Sprache L (K) kontextfrei.
   Zu K = ( X, Y, Z, h, z₀, S,  ) wird unter der Annahme  L (K) die kontextfreie Grammatik G = ( M, X, R, S ) konstruiert , wofür
   M = X  Y  { [ z, y, z´]  y  Y, z, z´  Z } und R = R_S R_X mit
   R_S = { (S, [ z₀, y, z ] )  y  Y, z  Z } und
   R_X = { ( [ z, y, z´] , x[ zⁿ , yⁿ , z^n-1 ] [ z^n-1 , y^n-1 , z^n-2 ] ... [ z¹ , y¹ , z´])  n  0 , z, z´, zⁱ Z, x  X  { }, und (zⁿ , y¹ ... yⁿ )  h (x, z, y)}. Man kann zeigen, daß für die so gewählte Grammatik [z₀, S, z´]  p  X* genau dann gilt, wenn (p, z₀, S) * ( , z´,  ) . Da mit den Regeln aus R_S die Ableitung S  [ z₀, S, z´] erzeugt werden kann, folgt schließlich p  L (K) genau dann, wenn S  p  L (G) . Für  L (K) ist noch eine entsprechende Regel in G zu ergänzen.

Folgerung: Zu jedem Kellerautomat kann ein Kellerautomat mit einem Zustand

angegeben werden, der dieselbe Sprache akzeptiert. (Die dem Satz entsprechende Konstruktion dieses Kellerautomat geht zu Lasten des Kellerumfangs.)

Definition: Deterministischer Kellerautomat, deterministisch kontextfreie Sprache Ein Kellerautomat K = ( X, Y, Z, h, z0, S, F ) heißt deterministisch , falls zu jeder Konfiguration k höchstens eine Folgekonfiguration k´ mit k  k´ existiert. Eine formale Sprache L heißt deterministisch kontextfrei, falls ein deterministischer Kellerautomat K mit LF ( K ) = L existiert.

Satz: Durchschnitt mit regulären Sprachen Wenn L  X* (deterministisch) kontextfrei und R  X* regulär, dann ist L  R (deterministisch) kontextfrei.

 

Beweis: Zu den nach Voraussetzung existierenden (deterministischen) Kellerautomat

K = ( X, Y, Z, h, z₀, S, F ) und endlichen Automaten A = ( X, Z´, f, z₀´, Z_F´) mit
L = L_F(K) und R = L(A) konstruieren wir den (deterministischen) Kellerautomat K´= ( X, Y, Z´´, h´, z₀´, S, F´´), wo Z´´= Z  Z´, z₀´´= [ z₀, z₀´], F´´= F  Z_F´ und
( [,´] , q )  h´( x, y, [ z, z´] ) falls (, q)  h ( x, y, z ) und f( x, z´) = ´,
( [,´], q )  h´( , y, [ z, z´]) falls (, q)  h ( , y, z).

Dann kann man zeigen:

L_F´´( K´) = L_F( K )  L ( A ) , denn für p  X* , q  Y*,  F, ´ Z_F´ ist
(p, [ z₀, z₀´], S)( , [,´], q) gdw. (p, z₀, S)  ( ,, q) und f(p,z₀) = ´.

Beweis: Zu den nach Voraussetzung existierenden (deterministischen) Kellerautomat

K = ( X, Y, Z, h, z₀, S, F ) mit L = L_F(K) konstruieren wir den (deterministischen) Kellerautomat K´= ( X, Y, Z´, h´, [ z₀,  ] , S, F  {  } ) mit
Z´= Z  { p  existiert p´* ,  mit f () = p´p } und
h´(, y, [ z,  ] ) = { ( [ z, f () ] , y ) , y  Y } ,
d.h., zur Eingabe wird f () als Eingabe für K erzeugt, bzw.
h´(  , y, [ z, p ] } = { ( [, p ], q )  (, q )  h (  , y, z ) },
d.h., es werden  -Übergänge von K simuliert, bzw
h´(  , y, [ z, xp ] ) = { ( [ z, p ], q )  { z, q )  h ( x, y, z ) }, d.h., es werden Übergänge von K zur Eingabe x simuliert.

Dann kann gezeigt werden, daß für z_f F gilt:
(p,[z₀, ],S)  *K'( ,[z_f, ],q) gdw. (f(p),z₀,S) *K( , z_f, q), d.h. L_F (K´)=f^-1(L).

Definition: Min(L)= {p  p L und für alle q: wenn q L Anfangsstück von p, dann ist p=q} als die Menge aller Wörter aus L, für die kein echtes Anfangswort zu L gehört, wird als Minimum von L bezeichnet.

Beweis: Zu dem nach Voraussetzung existierenden deterministischen Kellerautomat

K = ( X, Y, Z, h, z₀, S, F ) mit L_F ( K ) = L konstruieren wir den deterministischen Kellerautomat K´=(X,Y,Z,h´,z₀,S,F) mit h´={h  X Y Z \ F}, d.h., aus h werden die von Endzuständen ausgehenden Übergänge gestrichen. Dann gilt:
L_F ( K´) = Min ( L ) .

Beispiel: Die Sprache L = { p  p  { a, b }* } wird durch die Grammatik mit den Regeln

S  aSa  bSb   erzeugt, ist also kontextfrei. Wenn wir annehmen, daß L deterministisch kontextfrei ist, dann wären L´ = L  (ab)⁺ (ba)* (ab)* (ba)⁺ = {(ab)^m (ba)ⁿ (ab)ⁿ (ba)^m  m  1,n  0 } und Min(L´) = { p  p  L´ und
n < m} auch deterministisch kontextfrei, woraus im Widerspruch zu früher die Kontextfreiheit von f^-1( Min ( L´)) = { a^m bⁿ aⁿ b^m 0  n < m } mit der homomorphen Substitution f (a) = ab , f (b) = ba folgen würde.

Folgerung: Nichtdeterministische Kellerautomat sind hinsichtlich der von ihnen akzep-

tierten Sprachen ausdruckstärker als deterministische Kellerautomat.

Beispiel: Die nicht reguläre Sprache L = { aⁿbaⁿ  n  0 } wird von dem deterministischen

Kellerautomat K = ({ a, b }, {S}, { z₀, z₁, z₂ }, h, z₀, S) mit
h(a, z₀, S) = (z₀, SS), h(b, z₀, S) = (z₁,  ), h(a, z₁, S) = (z₁,  ),
h (b, z₁, S) = (z₂, S), h( a, z₂, S) = ( z₂, S), h (b, z₂, S) = (z₂, S) zum leeren Keller im Zustand z₁ akzeptiert, d.h., L = L ( K ).

Folgerung: Deterministische Kellerautomat sind hinsichtlich der von ihnen akzeptierten

Sprachen ausdrucksstärker als endliche Automaten.

 

Satz: Eigenschaften deterministisch kontextfreier Sprachen Wenn L deterministisch kontextfrei und R regulär, dann ist die Quotientensprache L / R = { p  existiert q  R mit pq  L } deterministisch kontextfrei. Wenn L  X* deterministisch kontextfrei, dann ist auch ihr Komplement X* \ L deterministisch kontextfrei. Zu jeder deterministisch kontextfreien Sprache L existiert ein deterministischer Kellerautomat K ohne  -Übergänge für Endzustände mit L = LF ( K ) . Es gibt deterministische Kellerautomat K, wo L (K) nicht deterministisch kontextfrei ist. Deterministisch kontextfreie Sprachen sind nicht abgeschlossen unter Vereinigung, Verkettung, Iteration und Homomorphismen.