GNF pomeni normalno obliko Greibach. CFG (kontekstno prosta slovnica) je v GNF (normalna oblika Greibach), če vsa produkcijska pravila izpolnjujejo enega od naslednjih pogojev:

• Začetni simbol, ki generira ε. Na primer S → ε.
• Neterminal, ki generira terminal. Na primer A → a.
• Neterminal, ki generira terminal, ki mu sledi poljubno število neterminalov. Na primer S → aASB.

Na primer:

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

Produkcijska pravila slovnice G1 izpolnjujejo pravila, določena za GNF, zato je slovnica G1 v GNF. Vendar produkcijsko pravilo slovnice G2 ne izpolnjuje pravil, določenih za GNF, ko A → ε in B → ε vsebuje ε (samo začetni simbol lahko ustvari ε). Torej slovnica G2 ni v GNF.

Koraki za pretvorbo CFG v GNF

Korak 1: Pretvori slovnico v CNF.

dodajte niz java

Če podana slovnica ni v CNF, jo pretvorite v CNF. Za pretvorbo CFG v CNF se lahko obrnete na naslednjo temo: normalna oblika Chomskyja

pretvorba niza v int v Javi

2. korak: Če slovnica obstaja levo rekurzijo, jo odstranite.

Če kontekstno prosta slovnica vsebuje levo rekurzijo, jo odstranite. Za odpravo leve rekurzije se lahko obrnete na naslednjo temo: Leva rekurzija

3. korak: V slovnici pretvorite podano proizvodno pravilo v obliko GNF.

Če katero koli produkcijsko pravilo v slovnici ni v obliki GNF, ga pretvorite.

primer:

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

rešitev:

java string.format

Ker je podana slovnica G že v CNF in ni leve rekurzije, lahko preskočimo korak 1 in korak 2 ter neposredno preidemo na korak 3.

Produkcijsko pravilo A → SA ni v GNF, zato nadomestimo S → XB | AA v proizvodnem pravilu A → SA kot:

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

Produkcijsko pravilo S → XB in B → XBA ni v GNF, zato nadomestimo X → a v produkcijsko pravilo S → XB in B → XBA kot:

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

Zdaj bomo odstranili levo rekurzijo (A → AAA), dobili bomo:

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

Zdaj bomo odstranili ničelno proizvodnjo C → ε, dobili bomo:

številčenje abecede

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

Produkcijsko pravilo S → AA ni v GNF, zato nadomestimo A → aC | aBAC | a | aBA v proizvodnem pravilu S → AA kot:

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

Produkcijsko pravilo C → AAC ni v GNF, zato nadomestimo A → aC | aBAC | a | aBA v proizvodnem pravilu C → AAC kot:

 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 

Torej je to oblika GNF za slovnico G.