GNF står för Greibach normal form. En CFG (kontextfri grammatik) är i GNF (Greibach normal form) om alla produktionsregler uppfyller ett av följande villkor:

• En startsymbol som genererar ε. Till exempel, S → ε.
• En icke-terminal som genererar en terminal. Till exempel, A → a.
• En icke-terminal som genererar en terminal som följs av ett valfritt antal icke-terminaler. Till exempel, S → aASB.

Till exempel:

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

Produktionsreglerna för Grammatik G1 uppfyller reglerna som specificeras för GNF, så grammatiken G1 är i GNF. Produktionsregeln för Grammatik G2 uppfyller dock inte reglerna specificerade för GNF eftersom A → ε och B → ε innehåller ε (endast startsymbol kan generera ε). Så grammatiken G2 finns inte i GNF.

Steg för att konvertera CFG till GNF

Steg 1: Konvertera grammatiken till CNF.

Om den givna grammatiken inte är i CNF, konvertera den till CNF. Du kan hänvisa till följande ämne för att konvertera CFG till CNF: Chomsky normal form

Steg 2: Om grammatiken finns vänsterrekursion, eliminera den.

jframe

Om den kontextfria grammatiken innehåller vänsterrekursion, eliminera den. Du kan hänvisa till följande ämne för att eliminera vänsterrekursion: Vänsterrekursion

Steg 3: Konvertera den givna produktionsregeln i grammatiken till GNF-form.

Om någon produktionsregel i grammatiken inte är i GNF-form, konvertera den.

spärrade nummer

Exempel:

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

Lösning:

Eftersom den givna grammatiken G redan finns i CNF och det inte finns någon vänsterrekursion, så kan vi hoppa över steg 1 och steg 2 och gå direkt till steg 3.

Produktionsregeln A → SA finns inte i GNF, så vi ersätter S → XB | AA i produktionsregeln A → SA som:

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

Produktionsregeln S → XB och B → XBA finns inte i GNF, så vi ersätter X → a i produktionsregeln S → XB och B → XBA som:

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

Nu tar vi bort vänsterrekursion (A → AAA), vi får:

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

Nu tar vi bort nollproduktion C → ε, vi får:

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

Produktionsregeln S → AA finns inte i GNF, så vi ersätter 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 

Produktionsregeln C → AAC finns inte i GNF, så vi ersätter 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 

Därför är detta GNF-formen för grammatiken G.

gör medan loop i java