GNF står for Greibach normalform. En CFG (kontekstfri grammatik) er i GNF (Greibach normal form), hvis alle produktionsreglerne opfylder en af ​​følgende betingelser:

• Et startsymbol, der genererer ε. For eksempel S → ε.
• En ikke-terminal, der genererer en terminal. For eksempel A → a.
• En ikke-terminal, der genererer en terminal, som efterfølges af et hvilket som helst antal ikke-terminaler. For eksempel S → aASB.

For eksempel:

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

Produktionsreglerne for Grammar G1 opfylder reglerne specificeret for GNF, så grammatikken G1 er i GNF. Produktionsreglen for Grammatik G2 opfylder dog ikke reglerne specificeret for GNF, da A → ε og B → ε indeholder ε (kun startsymbol kan generere ε). Så grammatikken G2 er ikke i GNF.

Trin til konvertering af CFG til GNF

Trin 1: Konverter grammatikken til CNF.

Hvis den givne grammatik ikke er i CNF, konverter den til CNF. Du kan henvise til følgende emne for at konvertere CFG til CNF: Chomsky normal form

Trin 2: Hvis grammatikken eksisterer venstre rekursion, skal du eliminere den.

Hvis den kontekstfri grammatik indeholder venstre rekursion, skal du eliminere den. Du kan henvise til følgende emne for at eliminere venstre rekursion: Venstre rekursion

Trin 3: I grammatikken skal du konvertere den givne produktionsregel til GNF-form.

Hvis en produktionsregel i grammatikken ikke er i GNF-form, skal du konvertere den.

Eksempel:

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

Løsning:

Da den givne grammatik G allerede er i CNF, og der ikke er nogen venstrerekursion, kan vi springe trin 1 og 2 over og gå direkte til trin 3.

Produktionsreglen A → SA er ikke i GNF, så vi erstatter S → XB | AA i produktionsreglen A → SA som:

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

Produktionsreglen S → XB og B → XBA er ikke i GNF, så vi erstatter X → a i produktionsreglen S → XB og B → XBA som:

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

Nu vil vi fjerne venstre rekursion (A → AAA), vi får:

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

Nu vil vi fjerne nulproduktion C → ε, vi får:

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

Produktionsreglen S → AA er ikke i GNF, så vi erstatter A → aC | aBAC | en | aBA i produktionsregel S → AA som:

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

Produktionsreglen C → AAC er ikke i GNF, så vi erstatter A → aC | aBAC | en | aBA i produktionsregel C → AAC som:

 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 

Derfor er dette GNF-formen for grammatikken G.

i orden