Theoretische Informatik

Konstruktion eines nichtdeterministischen Stackautomaten

aus einer kontextfreien Grammatik

 aufwärts

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.

Satz:  Zu jeder kontext­freien Grammatik G gibt es einen nicht­deterministischen Stack­automaten N, der die von G erzeugte Sprache L(G) erkennt.

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  enthalten in  Z  ×  E?  ×  H?  ×  H*  ×  Z.

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

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

sahw t

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

sahwn-1tn-1
tn-1εεwn-2tn-2
 ...     
t2εεw1t1
t1εεw0t

wobei t1, ..., tn-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 vereinigt 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

qεεSr

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

Xgeht über nachu

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

rεXur

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 Element T ein Tupel

raaεr

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

Sgeht über nachaY  |  aSY
Ygeht über nachb

Die Grammatik erzeugt die Sprache { anbn  |  n Element natürliche Zahlen }.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil
 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil
Stack

Eingabewort

   

 

sehh's'
 0 εεS1
 1 εSaY1
 1 εSaSY1
 1 εYb1
 1 aaε1
 1 bbε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

Sgeht über nachaSbS  |  ε

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

 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil
 
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil
Stack

Eingabewort

   

 

sehh's'
       
       
       
       
       

       






 

Weiter:  [CYK-Algorithmus]  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.01.2003   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