GNF znamená Greibach normálna forma. CFG (bezkontextová gramatika) je v GNF (normálna forma Greibach), ak všetky produkčné pravidlá spĺňajú jednu z nasledujúcich podmienok:

• Štartovací symbol generujúci ε. Napríklad S → ε.
• Neterminál generujúci terminál. Napríklad A → a.
• Neterminál generujúci terminál, za ktorým nasleduje ľubovoľný počet neterminálov. Napríklad S → aASB.

Napríklad:

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

Produkčné pravidlá gramatiky G1 spĺňajú pravidlá špecifikované pre GNF, takže gramatika G1 je v GNF. Avšak produkčné pravidlo gramatiky G2 nespĺňa pravidlá špecifikované pre GNF, pretože A → ε a B → ε obsahuje ε (iba počiatočný symbol môže generovať ε). Takže gramatika G2 nie je v GNF.

Kroky na premenu CFG na GNF

Krok 1: Preveďte gramatiku na CNF.

Ak daná gramatika nie je v CNF, preveďte ju do CNF. Ak chcete previesť CFG na CNF, pozrite si nasledujúcu tému: Chomského normálna forma

Krok 2: Ak gramatika existuje ľavá rekurzia, odstráňte ju.

Ak bezkontextová gramatika obsahuje ľavú rekurziu, odstráňte ju. Ak chcete odstrániť ľavú rekurziu, môžete si pozrieť nasledujúcu tému: Rekurzia vľavo

Krok 3: V gramatike preveďte dané produkčné pravidlo do tvaru GNF.

Ak niektoré produkčné pravidlo v gramatike nie je vo forme GNF, preveďte ho.

Príklad:

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

Riešenie:

Keďže daná gramatika G je už v CNF a neexistuje žiadna ľavá rekurzia, môžeme preskočiť krok 1 a krok 2 a prejsť priamo na krok 3.

Produkčné pravidlo A → SA nie je v GNF, preto dosadíme S → XB | AA vo výrobnom pravidle A → SA ako:

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

Produkčné pravidlo S → XB a B → XBA nie je v GNF, preto nahradíme X → a v produkčnom pravidle S → XB a B → XBA ako:

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

Teraz odstránime ľavú rekurziu (A → AAA), dostaneme:

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

Teraz odstránime nulovú produkciu C → ε, dostaneme:

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

Produkčné pravidlo S → AA nie je v GNF, preto dosadíme A → aC | aBAC | a | aBA v produkčnom pravidle S → AA ako:

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

Produkčné pravidlo C → AAC nie je v GNF, preto dosadíme A → aC | aBAC | a | aBA v produkčnom pravidle C → AAC ako:

 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 

Toto je teda forma GNF pre gramatiku G.