GNF staat voor Greibach-normaalvorm. Een CFG (contextvrije grammatica) is in GNF (Greibach-normaalvorm) als alle productieregels aan een van de volgende voorwaarden voldoen:

• Een startsymbool dat ε genereert. Bijvoorbeeld S → ε.
• Een niet-terminal die een terminal genereert. Bijvoorbeeld A → een.
• Een niet-terminal die een terminal genereert die wordt gevolgd door een willekeurig aantal niet-terminals. Bijvoorbeeld S → aASB.

Bijvoorbeeld:

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

De productieregels van Grammatica G1 voldoen aan de regels gespecificeerd voor GNF, dus de grammatica G1 is in GNF. De productieregel van Grammatica G2 voldoet echter niet aan de regels die zijn gespecificeerd voor GNF, aangezien A → ε en B → ε ε bevatten (alleen het startsymbool kan ε genereren). De grammatica G2 staat dus niet in GNF.

Stappen voor het omzetten van CFG naar GNF

Stap 1: Converteer de grammatica naar CNF.

software testen

Als de gegeven grammatica niet in CNF is, converteer deze dan naar CNF. U kunt het volgende onderwerp raadplegen om de CFG naar CNF om te zetten: Chomsky-normaalvorm

Stap 2: Als er sprake is van linkse recursie, elimineer deze dan.

Als de contextvrije grammatica linkse recursie bevat, elimineer deze dan. U kunt het volgende onderwerp raadplegen om linkse recursie te elimineren: Linkse recursie

actress zeenat aman

Stap 3: Converteer in de grammatica de gegeven productieregel naar GNF-vorm.

Als een productieregel in de grammatica niet in GNF-vorm is, converteer deze dan.

Voorbeeld:

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

Oplossing:

Omdat de gegeven grammatica G al in CNF staat en er geen linkse recursie is, kunnen we stap 1 en stap 2 overslaan en direct naar stap 3 gaan.

De productieregel A → SA zit niet in GNF, dus vervangen we S → XB | AA in de productieregel A → SA als:

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

De productieregel S → XB en B → XBA zit niet in GNF, dus vervangen we X → a in de productieregel S → XB en B → XBA als:

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

Nu verwijderen we de linkerrecursie (A → AAA), we krijgen:

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

Nu gaan we de nulproductie C → ε verwijderen, we krijgen:

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

De productieregel S → AA zit niet in GNF, dus vervangen we A → aC | aBAC | een | aBA in productieregel S → AA als:

Hoe verander je de string in int?

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

De productieregel C → AAC zit niet in GNF, dus vervangen we A → aC | aBAC | een | aBA in productieregel C → AAC als:

 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 

Daarom is dit de GNF-vorm voor de grammatica G.