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.