GNF reiškia Greibacho normaliąją formą. CFG (nekontekstinė gramatika) yra GNF (Greibacho normalioji forma), jei visos gamybos taisyklės atitinka vieną iš šių sąlygų:

• Pradžios simbolis, generuojantis ε. Pavyzdžiui, S → ε.
• Ne terminalas, generuojantis terminalą. Pavyzdžiui, A → a.
• Ne terminalas, generuojantis terminalą, po kurio seka bet koks ne terminalų skaičius. Pavyzdžiui, S → aASB.

Pavyzdžiui:

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

Gramatikos G1 gamybos taisyklės atitinka GNF nurodytas taisykles, todėl gramatika G1 yra GNF. Tačiau Gramatikos G2 gamybos taisyklė neatitinka GNF nustatytų taisyklių, nes A → ε ir B → ε yra ε (tik pradžios simbolis gali generuoti ε). Taigi gramatikos G2 nėra GNF.

CFG konvertavimo į GNF žingsniai

1 žingsnis: Konvertuokite gramatiką į CNF.

Jei nurodytos gramatikos nėra CNF, konvertuokite ją į CNF. Norėdami konvertuoti CFG į CNF, galite kreiptis į šią temą: Chomsky normali forma

2 žingsnis: Jei gramatikoje yra kairioji rekursija, pašalinkite ją.

Fibonacci serija java

Jei konteksto neturinčioje gramatikoje yra kairiosios rekursijos, pašalinkite ją. Norėdami pašalinti kairiąją rekursiją, galite kreiptis į šią temą: Kairioji rekursija

3 veiksmas: Gramatikoje nurodytą gamybos taisyklę konvertuokite į GNF formą.

Jei kuri nors gramatikos gamybos taisyklė nėra GNF forma, konvertuokite ją.

pašalinti angular cli

Pavyzdys:

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

Sprendimas:

Kadangi pateikta gramatika G jau yra CNF ir nėra kairiosios rekursijos, galime praleisti 1 ir 2 žingsnius ir pereiti tiesiai prie 3 žingsnio.

Gamybos taisyklė A → SA nėra GNF, todėl pakeičiame S → XB | AA gamybos taisyklėje A → SA kaip:

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

Gamybos taisyklė S → XB ir B → XBA nėra GNF, todėl gamybos taisyklėje S → XB ir B → XBA pakeičiame X → a kaip:

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

Dabar pašalinsime kairiąją rekursiją (A → AAA), gausime:

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

Dabar pašalinsime nulinę gamybą C → ε, gausime:

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

Gamybos taisyklė S → AA nėra GNF, todėl pakeičiame A → aC | aBAC | a | aBA gamybos taisyklėje S → AA kaip:

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

Gamybos taisyklė C → AAC nėra GNF, todėl pakeičiame A → aC | aBAC | a | aBA gamybos taisyklėje C → AAC kaip:

 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 

Taigi, tai yra GNF forma gramatikai G.

myflixr