Theoretische Informatik

Normalisierung von kontextfreien Grammatiken

 aufwärts

Bei einer kontext­freien Grammatik bestehen die linken Seiten aller Produktionen jeweils nur aus einer einzigen Variablen. Für die rechten Seiten der Produktionen bestehen dagegen keine Ein­schränkungen.

Oft ist es wünschens­wert, dass auch die rechten Seiten eine bestimmte Form haben. Durch geeignete Umformung der Grammatik ist es möglich, die rechten Seiten der Produktionen in eine bestimmte Form zu bringen, ohne dass sich die von der Grammatik erzeugte Sprache ändert. Beispiels­weise lassen sich bei Bedarf alle Ketten­produktionen, also Produktionen der Form Xgeht über nachY beseitigen.

Ein solcher Prozess wird als Normalisierung bezeichnet. Zunächst führen wir eine Basis-Normalisierung durch. Nach weiteren Normalisierungs­schritten stehen am Ende die Chomsky-Normalform oder die Greibach-Normalform für kontextfreie Grammatiken.

Äquivalenz von Grammatiken

Definition:  Zwei Grammatiken G und G' werden als äquivalent bezeichnet, wenn sie dieselbe Sprache erzeugen, d.h. wenn gilt

L(G)  =  L(G')

Beispiel:  Die Grammatik G0 mit den Produktionen

Sgeht über nachaSb  |  ε

und die Grammatik G1 mit den Produktionen

Sgeht über nachC
Cgeht über nachD
Egeht über nachab
Dgeht über nachS  |  aSb  |  aF  |  ε

sind äquivalent, denn beide erzeugen die Sprache { anbn  |  n Element natürliche Zahlen0 }, wenn auch letztere auf etwas umständliche Weise.

Nutzlose Variablen

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik und sei A = V vereinigt T. Eine Variable X Element V heißt

Satz:  Zu jeder kontext­freien Grammatik G = (V, T, P, S) gibt es eine äquivalente kontextfreie Grammatik G' = (V', T, P', S) ohne nutzlose Variablen.

Beweis:  Sei w ein Wort mit w Element L(G). Dann gibt es eine Ableitungs­folge S grammatikalische Ableitung w. Jede Variable, die in den Ableitungs­schritten auftritt, ist erreichbar und produktiv. In keiner Ableitungs­folge kann eine nutzlose Variable vorkommen.

G' geht aus G hervor, indem aus V alle nutzlosen Variablen entfernt werden und aus P alle Produktionen, in denen nutzlose Variablen vorkommen.

Beispiel:  In der Grammatik G1 ist die Variable E nicht erreichbar und die Variable F nicht produktiv, beide Variablen sind also nutzlos. Diese Variablen und die zugehörigen Produktionen werden daher entfernt. Es verbleibt die Grammatik G2:

Sgeht über nachC
Cgeht über nachD
Dgeht über nachS  |  aSb  |  ε

Rekursives Startsymbol

Definition:  Sei G = (V, T, P, S) eine Grammatik und sei A = V vereinigt T. Eine Variable X Element V heißt rekursiv, wenn

X  grammatikalische Ableitung  uXv

mit u, v Element A* gilt.

Beispiel:  In der Grammatik G3 des obigen Beispiels ist das Startsymbol S rekursiv.

Satz:  Zu jeder Grammatik G = (V, T, P, S) gibt es eine äquivalente Grammatik G' = (V', T, P', S'), deren Startsymbol S' nicht rekursiv ist.

Beweis:  Die Grammatik G' geht aus der Grammatik G hervor, indem ein neues Startsymbol S' zur Menge der Variablen V hinzugefügt wird und die neue Produktion S'geht über nachS zur Menge der Produktionen P hinzugefügt wird.

Beispiel:  Indem die angegebene Vorgehens­weise auf die Grammatik G2 angewendet wird, ergibt sich folgende Grammatik G3, deren Startsymbol S' nicht rekursiv ist:

S'geht über nachS
Sgeht über nachC
Cgeht über nachD
Dgeht über nachS  |  aSb  |  ε

Epsilon-Produktionen

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik. Eine Produktion der Form

Xgeht über nachε

mit X Element V wird als Epsilon-Produktion bezeichnet.

Satz:  Zu jeder kontext­freien Grammatik G = (V, T, P, S) gibt es eine äquivalente kontextfreie Grammatik G' = (V, T, P', S')

Beweis:  Die kontextfreie Grammatik G wird durch folgendes Verfahren in die Grammatik G' umgeformt.

  1. führe die Produktion S'geht über nachS ein, damit das Startsymbol nicht rekursiv ist
  2. bestimme alle Variablen X, aus denen sich das leere Wort ε ableiten lässt:

    Vε  =  { X Element V  |  X grammatikalische Ableitung ε }

  3. entferne alle Epsilon-Produktionen aus der Grammatik
  4. wiederhole solange Ygeht über nachuXv mit X Element Vε und |uv|größer gleich1 eine Produktion ist, aber Ygeht über nachuv noch keine Produktion ist

    führe die Produktion Ygeht über nachuv zusätzlich ein

  5. wenn S' Element Vε dann

    führe die Produktion S'geht über nachε ein

Beispiel:  In der Grammatik G3 hatten wir Schritt 1 des Verfahrens bereits durchgeführt. In Schritt 2 bestimmen wir nun Vε  =  { S', S, C, D }. In Schritt 3 entfernen wir die Produktion Dgeht über nachε. In Schritt 4 finden wir Dgeht über nachaSb als einzige Produktion mit der dort angegebenen Eigenschaft und führen daher die Produktion Dgeht über nachab neu ein. Und in Schritt 5 schließlich führen wir noch die Produktion S'geht über nachε ein, da S' Element Vε.

Das Ergebnis ist die Grammatik G4:

S'geht über nachS  |  ε
Sgeht über nachC
Cgeht über nachD
Dgeht über nachS  |  aSb  |  ab

Kettenproduktionen

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik. Eine Produktion der Form

Xgeht über nachY

mit X, Y Element V wird als Ketten­produktion bezeichnet.

Satz:  Zu jeder kontext­freien Grammatik G = (V, T, P, S) gibt es eine äquivalente kontextfreie Grammatik G' = (V', T, P', S) ohne Ketten­produktionen.

Beweis:  Ein Sonderfall von Ketten­produktionen sind Zyklen von Ketten­produktionen. Diese Zyklen werden zuerst entfernt.

Zyklen von Ketten­produktionen entfernen

Wenn die Grammatik einen Zyklus der Form

X0 Pfeil nach rechts X1,  X1 Pfeil nach rechts X2,   ... ,  Xk-1 Pfeil nach rechts X0,   k Element natürliche Zahlen

enthält, so lassen sich die Variablen Xi alle ineinander überführen und brauchen daher nicht unter­schieden zu werden. Es werden daher die Produktionen des Zyklus entfernt und alle weiteren Vorkommen der Xi in G durch einen einzigen Repräsentanten ersetzt (falls das Startsymbol S im Zyklus vorkommt, durch S).

 

Ketten­produktionen entfernen

Jede Ketten­produktion Xgeht über nachY wird in der Weise umgeformt, dass für Y die aus Y direkt ableitbaren rechten Seiten eingesetzt werden, so lange, bis keine Ketten­produktionen mehr vorhanden sind.

Beispiel:  

In der Grammatik G4 ist Sgeht über nachC, Cgeht über nachD, Dgeht über nachS ein Zyklus von Ketten­produktionen. Wir entfernen die Produktionen des Zyklus und ersetzen alle weiteren Vorkommen von S und D durch C. Das Ergebnis ist die Grammatik G5:

S'geht über nachC  |  ε
Cgeht über nachaCb  |  ab

 

Die Ketten­produktion S'geht über nachC entfernen wir, indem für deren rechte Seite C die aus C direkt ableitbaren Wörter einsetzen. Es ergibt sich die Grammatik G6:

S'geht über nachaCb  |  ab  |  ε
Cgeht über nachaCb  |  ab

Basis-Normalisierung

Die eben beschriebenen Umformungen lassen sich zusammen anwenden, diesen Prozess bezeichnen wir als Basis-Normalisierung:

  1. Nutzlose Variablen entfernen
  2. Rekursives Startsymbol entfernen
  3. Epsilon-Produktionen entfernen, mit Ausnahme ggf. der Produktion S'geht über nachε
  4. Ketten­produktionen entfernen

Definition:  Sei G = (V, T, P, S) eine kontextfreie Grammatik. Wir bezeichnen die Grammatik als basis-normalisiert, wenn sie keine keine nutzlosen Variablen, kein rekursives Startsymbol, keine Epsilon-Produktionen außer Sgeht über nachε und keine Ketten­produktionen enthält.

Beispiel:  Die obige Grammatik G6 ist basis-normalisiert.

Eine basis-normalisierte kontextfreie Grammatik lässt sich durch weitere Normalisierungs­schritte in die Chomsky-Normalform oder in die Greibach-Normalform umformen.

 

Weiter mit:  [Chomsky-Normalform]   [Greibach-Normalform]   oder   up

 

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