GNF tarkoittaa Greibachin normaalimuotoa. CFG (kontekstivapaa kielioppi) on GNF:ssä (Greibachin normaalimuodossa), jos kaikki tuotantosäännöt täyttävät yhden seuraavista ehdoista:

• Aloitussymboli, joka tuottaa ε:n. Esimerkiksi S → ε.
• Ei-päätelaite, joka tuottaa päätelaitteen. Esimerkiksi A → a.
• Ei-päätelaite, joka luo päätelaitteen, jota seuraa mikä tahansa määrä ei-päätteitä. Esimerkiksi S → aASB.

Esimerkiksi:

kromi osoitepalkki

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

Kieliopin G1 tuotantosäännöt täyttävät GNF:lle määritellyt säännöt, joten kielioppi G1 on GNF:ssä. Grammar G2:n tuotantosääntö ei kuitenkaan täytä GNF:lle määritettyjä sääntöjä, koska A → ε ja B → ε sisältää ε:n (vain aloitussymboli voi tuottaa ε:n). Joten kielioppi G2 ei ole GNF:ssä.

Vaiheet CFG:n muuntamiseksi GNF:ksi

Vaihe 1: Muunna kielioppi CNF:ksi.

Jos annettu kielioppi ei ole CNF:ssä, muunna se CNF:ksi. Voit käyttää seuraavaa aihetta muuntaaksesi CFG:n CNF:ksi: Chomsky-normaali muoto

Vaihe 2: Jos kielioppi sisältää vasemman rekursion, poista se.

Jos kontekstiton kielioppi sisältää vasemmanpuoleisen rekursion, poista se. Voit käyttää seuraavaa aihetta poistaaksesi vasemmanpuoleisen rekursion: Vasen rekursio

iskcon täysi lomake

Vaihe 3: Muunna kielioppissa annettu tuotantosääntö GNF-muotoon.

Jos jokin kieliopin tuotantosääntö ei ole GNF-muodossa, muunna se.

Esimerkki:

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

Ratkaisu:

Koska annettu kielioppi G on jo CNF:ssä eikä siinä ole vasenta rekursiota, voimme ohittaa vaiheet 1 ja 2 ja siirtyä suoraan vaiheeseen 3.

Tuotantosääntö A → SA ei ole GNF:ssä, joten korvaamme S → XB | AA tuotantosäännössä A → SA seuraavasti:

merkkijonotaulukko

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

Tuotantosäännöt S → XB ja B → XBA eivät ole GNF:ssä, joten korvaamme X → a tuotantosäännössä S → XB ja B → XBA seuraavasti:

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

Nyt poistamme vasemman rekursion (A → AAA), saamme:

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

Nyt poistamme nollatuotannon C → ε, saamme:

aakkosten numerointi

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

Tuotantosääntö S → AA ei ole GNF:ssä, joten korvaamme A → aC | aBAC | a | aBA tuotantosäännössä S → AA muodossa:

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

Tuotantosääntö C → AAC ei ole GNF:ssä, joten korvaamme A → aC | aBAC | a | aBA tuotantosäännössä C → AAC muodossa:

 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 

Siksi tämä on GNF-muoto kieliopin G:lle.