Theoretische Informatik

Gegeben ist eine kontextfreie Grammatik G und ein Wort w. Es stellt sich die Frage, ob w zu L(G) gehört, ob also die von G erzeugte Sprache das Wort w enthält. Um dies zu entscheiden, wird aus der kontext­freien Grammatik G ein nicht­deterministischer Stackautomat N konstruiert. Der Automat wird so konstruiert, dass er genau alle jene Wörter akzeptiert, die zu L(G) gehören.

Zum Beweis des Satzes konstruieren wir aus einer beliebig gegebenen kontext­freien Grammatik G einen (erweiterten) nicht­deterministischen Stack­automaten, der die von G erzeugte Sprache durch leeren Stack erkennt.

Erweiterter nichtdeterministischer Stackautomat

Wir erweitern die Definition des nicht­deterministischen Stack­automaten in der Weise, dass wir die Übergangs­relation definieren als

d  ⊆  Z  ×  E^?  ×  H^?  ×  H*  ×  Z.

Hierbei ist Z die Zustands­menge, E das Eingabe­alphabet und E^? = E ∪ {ε}, H das Stack­alphabet und H^? = H ∪ {ε}.

Die neue Übergangs­relation kann also in einem Schritt eine ganzes Wort w von Stackzeichen auf dem Stack ablegen. Dies geschieht so, dass dieses Wort zeichenweise, mit dem letzten Zeichen zuerst, in den Stack geschrieben wird. Das erste Zeichen von w erscheint als oberstes Stackzeichen.

Offenbar sind der normale Stackautomat und der erweiterte Stackautomat äquivalente Maschinen, denn einerseits ist der normale Stackautomat ein Spezialfall des erweiterten Stack­automaten, andererseits lässt sich jeder erweiterte Stackautomat in ein normalen Stack­automaten umformen, indem ein erweiterter Zustands­übergang in eine Folge von normalen Zustands­übergängen zerlegt wird, wobei zusätzliche Zustände eingeführt werden.

So wird jeder erweiterte Zustands­übergang

mit w = w₀ ... w_n-1, n > 1 ersetzt durch die normalen Zustands­übergänge

wobei t₁, ..., t_n-1 als neue Zustände eingeführt werden.

Konstruktion

Wir konstruieren aus der Grammatik G = (V, T, P, S) einen erweiterten nicht­deterministischen Stack­automaten N = (Z, E, H, d, q, F) mit

Z  =  {q, r}

E  =  T

H  =  V ∪ T

Die Übergangs­relation d enthält Tupel (s, a, h, h', s') bestehend aus dem aktuellem Zustand s, dem gelesenen Eingabe­zeichen a, dem vom Stack entfernten Stackzeichen h, dem auf dem Stack neu abgelegten Wort h' und dem neuen Zustand s'.

Die Übergangs­relation wird wie folgt konstruiert. Zunächst wird ein Tupel

eingeführt. Wenn der Stackautomat zu arbeiten beginnt, legt er also zuerst das Startsymbol S der Grammatik auf den Stack und geht in den Zustand r über. Der Zustand r ist der einzige Zustand außer dem Startzustand q; der Stackautomat benötigt keine weiteren Zustände.

Dann wird für jede Produktion

Xu

der Grammatik ein ent­sprechendes Tupel zur Übergangs­relation d hinzugefügt, und zwar

Wenn der Stackautomat also die linke Seite X einer Produktion auf dem Stack vorfindet, ersetzt er sie nicht­deterministisch durch eine zugehörige rechte Seite u.

Ferner wird für jedes Terminal­zeichen a ∈ T ein Tupel

eingeführt.

Wenn der Stackautomat also das Zeichen a liest und er gleichzeitig das Zeichen a auf dem Stack vorfindet, entfernt er es vom Stack.

Die Arbeitsweise des so konstruierten Stack­automaten bildet genau den Ersetzungs­mechanismus der Grammatik nach. Daher erkennt der Stackautomat genau die von der Grammatik erzeugte Sprache.

Beispiel:  Gegeben sei die Grammatik G = (V, T, P, S) mit T = {a, b} und den Produktionen

S		aY  |  aSY
Y		b

Die Grammatik erzeugt die Sprache { aⁿbⁿ  |  n ∈ ℕ }.

Der erweiterte Stackautomat hat die Zustände q = 0 und r = 1 und enthält folgende Zustands­übergänge (s, a, h, h', s'):

 

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Stack

Eingabewort

   

 

s	e	h	h'	s'
0	ε	ε	S	1
1	ε	S	aY	1
1	ε	S	aSY	1
1	ε	Y	b	1
1	a	a	ε	1
1	b	b	ε	1

Wenn der Stackautomat beispiels­weise das Wort aabb abarbeitet, schreibt er zunächst das Startsymbol S in den Stack. Er findet dann S im Stack vor und ersetzt S durch aSY, ohne ein Zeichen der Eingabe zu lesen. Nun befindet sich a als oberstes Zeichen auf dem Stack. Der Stackautomat liest a und entfernt a vom Stack. Nun ist S das oberste Zeichen auf dem Stack. Ohne ein Zeichen zu lesen, ersetzt der Stackautomat diesmal S durch aY. Der Stackinhalt ist jetzt aYY und a ist das oberste Zeichen. Wieder liest der Stackautomat ein a und entfernt a vom Stack. Anschließend ersetzt er Y durch b, liest b und entfernt b, ersetzt das verbleibende Y durch b und liest b und entfernt b. Nun ist die Eingabe vollständig abgearbeitet und der Stack ist leer. Somit akzeptiert der Stackautomat das Wort aabb durch leeren Stack.

Aufgabe

Aufgabe 1:  Gegeben sei die Grammatik G = (V, T, P, S) mit den Produktionen

S

aSbS  |  ε

Geben Sie die Übergangs­relation d eines erweiterten nicht­deterministischen Stack­automaten an, der L(G) erkennt.

Probieren Sie aus, wie der Stackautomat das Wort abab abarbeitet.

 

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Stack

Eingabewort

   

 

s	e	h	h'	s'