GNF står for Greibach normalform. En CFG (kontekstfri grammatikk) er i GNF (Greibach normal form) hvis alle produksjonsreglene tilfredsstiller en av følgende betingelser:

• Et startsymbol som genererer ε. For eksempel S → ε.
• En ikke-terminal som genererer en terminal. For eksempel A → a.
• En ikke-terminal som genererer en terminal som etterfølges av et hvilket som helst antall ikke-terminaler. For eksempel S → aASB.

For eksempel:

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

Produksjonsreglene til Grammar G1 tilfredsstiller reglene spesifisert for GNF, så grammatikken G1 er i GNF. Produksjonsregelen til Grammatikk G2 tilfredsstiller imidlertid ikke reglene spesifisert for GNF som A → ε og B → ε inneholder ε (bare startsymbolet kan generere ε). Så grammatikken G2 er ikke i GNF.

Trinn for å konvertere CFG til GNF

Trinn 1: Konverter grammatikken til CNF.

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

Steg 2: Hvis grammatikken eksisterer venstre rekursjon, eliminer den.

Hvis kontekstfri grammatikk inneholder venstrerekursjon, eliminer den. Du kan henvise til følgende emne for å eliminere venstre rekursjon: Venstre rekursjon

Trinn 3: I grammatikken, konverter den gitte produksjonsregelen til GNF-form.

Hvis en produksjonsregel i grammatikken ikke er i GNF-form, konverter den.

Eksempel:

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

Løsning:

Siden den gitte grammatikken G allerede er i CNF og det ikke er noen venstrerekursjon, kan vi hoppe over trinn 1 og trinn 2 og gå direkte til trinn 3.

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

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

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

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

Nå skal vi fjerne venstre rekursjon (A → AAA), vi får:

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

Nå skal vi fjerne nullproduksjon C → ε, vi får:

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

Produksjonsregelen S → AA er ikke i GNF, så vi erstatter A → aC | aBAC | en | aBA i produksjonsregel 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 

Produksjonsregelen C → AAC er ikke i GNF, så vi erstatter A → aC | aBAC | en | aBA i produksjonsregel 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 rekkefølge