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