logo

Greibach-Normalform (GNF)

GNF steht für Greibach-Normalform. Eine CFG (kontextfreie Grammatik) liegt in GNF (Greibach-Normalform) vor, wenn alle Produktionsregeln eine der folgenden Bedingungen erfüllen:

  • Ein Startsymbol, das ε erzeugt. Zum Beispiel S → ε.
  • Ein Nicht-Terminal, das ein Terminal generiert. Zum Beispiel A → a.
  • Ein Nicht-Terminal, das ein Terminal generiert, dem eine beliebige Anzahl von Nicht-Terminals folgt. Zum Beispiel S → aASB.

Zum Beispiel:

 G1 = aB, A → aA G2 = S → aAB 

Die Produktionsregeln der Grammatik G1 erfüllen die für GNF angegebenen Regeln, sodass die Grammatik G1 in GNF enthalten ist. Die Produktionsregel der Grammatik G2 erfüllt jedoch nicht die für GNF festgelegten Regeln, da A → ε und B → ε ε enthält (nur das Startsymbol kann ε erzeugen). Die Grammatik G2 ist also nicht in GNF enthalten.

Schritte zum Konvertieren von CFG in GNF

Schritt 1: Konvertieren Sie die Grammatik in CNF.

s in Python

Wenn die angegebene Grammatik nicht in CNF vorliegt, konvertieren Sie sie in CNF. Sie können sich auf das folgende Thema beziehen, um CFG in CNF umzuwandeln: Chomsky-Normalform

Schritt 2: Wenn die Grammatik eine Linksrekursion aufweist, beseitigen Sie sie.

Wenn die kontextfreie Grammatik eine Linksrekursion enthält, beseitigen Sie diese. Sie können sich auf das folgende Thema beziehen, um die Linksrekursion zu beseitigen: Linksrekursion

Schritt 3: Konvertieren Sie in der Grammatik die gegebene Produktionsregel in die GNF-Form.

Wenn eine Produktionsregel in der Grammatik nicht in GNF-Form vorliegt, konvertieren Sie sie.

Beispiel:

 S → XB | AA A → a | SA B → b X → a 

Lösung:

Gimp-Rechteck zeichnen

Da sich die gegebene Grammatik G bereits in CNF befindet und es keine Linksrekursion gibt, können wir Schritt 1 und Schritt 2 überspringen und direkt mit Schritt 3 fortfahren.

Die Produktionsregel A → SA ist nicht in GNF enthalten, daher ersetzen wir S → XB | AA in der Produktionsregel A → SA als:

 S → XB | AA A → a | XBA | AAA B → b X → a 

Die Produktionsregel S → XB und B → XBA ist nicht in GNF enthalten, daher ersetzen wir X → a in der Produktionsregel S → XB und B → XBA wie folgt:

 S → aB | AA A → a | aBA | AAA B → b X → a 

Jetzt entfernen wir die Linksrekursion (A → AAA) und erhalten:

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Jetzt entfernen wir die Nullproduktion C → ε und erhalten:

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

Die Produktionsregel S → AA ist nicht in GNF enthalten, daher ersetzen wir A → aC | aBAC | ein | aBA in der Produktionsregel S → AA als:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

Die Produktionsregel C → AAC ist nicht in GNF enthalten, daher ersetzen wir A → aC | aBAC | ein | aBA in der Produktionsregel C → AAC als:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

Daher ist dies die GNF-Form für die Grammatik G.