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.