Theoretische Informatik

Gegeben ist ein nichtdeterministischer endlicher Automat N. Es stellt sich die Frage, ob es eine Grammatik G gibt mit L(G) = L(N). Gesucht ist also eine Grammatik, die genau die Sprache erzeugt, die der Automat N erkennt. Wir formen dazu den gegebenen nichtdeterministischen Automaten N in geeigneter Weise in eine Grammatik um. Dabei zeigt es sich, dass sogar ein ganz bestimmter Typ von Grammatik hierfür ausreichend ist. Ferner zeigt sich, dass "Erkennen" und "Erzeugen" im Prinzip das gleiche ist, nur in entgegengesetzter Richtung.

Verfahren

Gegeben sei ein nichtdeterministischer endlicher Automat

N  =  (Z, A, d, q, F)

mit Zustandsmenge Z, Eingabealphabet A, Übergangsrelation d, Startzustand q und Menge von Endzuständen F.

Aus dem Automaten N wird in folgender Weise eine Grammatik

G = (V, T, P, S)

mit Variablenmenge V, Terminalzeichenmenge T, Produktionenmenge P und Startsymbol S konstruiert.

Konstruktion der Grammatik

1. Die Menge der Variablen V der Grammatik ist gleich der Menge der Zustände Z des Automaten:

   V  =  Z

2. Das Startsymbol S der Grammatik ist gleich dem Startzustand q des Automaten:

   S  =  q

3. Die Menge der Terminalzeichen T der Grammatik ist gleich dem Eingabealphabet A des Automaten:

   T  =  A

4. Die Menge der Produktionen P der Grammatik entsteht aus der Übergangsrelation d des Automaten wie folgt:
   1. Für alle a ∈ A und r, s ∈ Z gilt

      (r, a, s) ∈ d   ⇔   r → as  ∈  P

   2. Für alle r ∈ Z gilt

      r ∈ F   ⇔   r → ε  ∈  P

   Aus jedem Element (r, a, s) der Übergangsrelation wird also eine Produktion r → as gemacht. Zusätzlich wird für jeden Endzustand r ∈ F noch eine Produktion r → ε erzeugt.

Jedem Wort, das der Automat erkennt, entspricht ein Pfad durch den Zustandsgraphen des Automaten vom Startzustand zu einem Endzustand. Diesem Pfad entspricht eine Ableitungsfolge vom Startsymbol der Grammatik zu diesem Wort. Umgekehrt entspricht jeder Ableitungsfolge vom Startsymbol der Grammatik zu einem Terminalwort ein Pfad durch den Zustandsgraphen des Automaten vom Startzustand zu einem Endzustand.

Beispiel:  Der in folgendem Bild 1 dargestellte nichtdeterministische endliche Automat N erkennt die Sprache

L  =  { alle Wörter über A = {a, b}, die mit a anfangen und mit a aufhören }

Die aus dem Automaten N konstruierte Grammatik G = (V, T, P, S) hat die Variablen V = {S, X, Y}, die Terminalzeichen T = {a, b}, die Produktionen

S		aX  |  aY
X		aX  |  bX  |  aY
Y		ε

und das Startsymbol S. Die Grammatik erzeugt die Sprache L.

 

Dem Wort abba entspricht der Pfad von S über X nach Y im Automaten. Diesem Pfad entspricht die Ableitungsfolge

S → aX → abX → abbX → abbaY → abba

in der Grammatik.

Rechtslineare Grammatik

Die Grammatik, die durch die angegebene Konstruktion entsteht, ist eine rechtslineare Grammatik.

Definition:  Eine Grammatik G = (V, T, P, S) heißt rechtslinear, wenn jede Produktion von der Form

X		aY	oder
X		a	oder
X		ε

mit X, Y ∈ V und a ∈ T ist.

Eine rechtslineare Grammatik ist nichts anderes als eine Typ-3-Grammatik der Chomsky-Hierarchie.

Aufgaben