GNF je kratica za Greibach normalni oblik. CFG (gramatika bez konteksta) je u GNF (Greibach normalan oblik) ako sva pravila proizvodnje zadovoljavaju jedan od sljedećih uvjeta:

• Početni simbol koji generira ε. Na primjer, S → ε.
• Neterminal koji generira terminal. Na primjer, A → a.
• Ne-terminal koji generira terminal iza kojeg slijedi bilo koji broj ne-terminala. Na primjer, S → aASB.

Na primjer:

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

Pravila proizvodnje gramatike G1 zadovoljavaju pravila navedena za GNF, tako da je gramatika G1 u GNF-u. Međutim, proizvodno pravilo Gramatike G2 ne zadovoljava pravila navedena za GNF jer A → ε i B → ε sadrži ε (samo početni simbol može generirati ε). Dakle, gramatika G2 nije u GNF.

sortirana tuple python

Koraci za pretvaranje CFG u GNF

Korak 1: Pretvorite gramatiku u CNF.

Ako data gramatika nije u CNF, pretvorite je u CNF. Možete pogledati sljedeću temu za pretvaranje CFG u CNF: Chomsky normalni oblik

Korak 2: Ako gramatika postoji lijevu rekurziju, eliminirajte je.

Ako gramatika bez konteksta sadrži lijevu rekurziju, uklonite je. Možete pogledati sljedeću temu kako biste uklonili lijevu rekurziju: Lijeva rekurzija

Korak 3: U gramatici pretvorite zadano proizvodno pravilo u GNF oblik.

primjer liste u Javi

Ako bilo koje proizvodno pravilo u gramatici nije u GNF obliku, pretvorite ga.

sat matematike java

Primjer:

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

Riješenje:

Kako je navedena gramatika G već u CNF-u i nema lijeve rekurzije, možemo preskočiti korak 1 i korak 2 i izravno prijeći na korak 3.

Proizvodno pravilo A → SA nije u GNF, pa zamjenjujemo S → XB | AA u proizvodnom pravilu A → SA kao:

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

Pravilo proizvodnje S → XB i B → XBA nije u GNF-u, pa X → a zamjenjujemo u pravilu proizvodnje S → XB i B → XBA kao:

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

Sada ćemo ukloniti lijevu rekurziju (A → AAA), dobivamo:

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

Sada ćemo ukloniti nultu proizvodnju C → ε, dobivamo:

numeriranje abecede

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

Produkcijsko pravilo S → AA nije u GNF, pa zamjenjujemo A → aC | aBAC | a | aBA u pravilu proizvodnje S → AA kao:

 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 nije u GNF, pa zamjenjujemo A → aC | aBAC | a | aBA u proizvodnom pravilu C → AAC kao:

 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 

Dakle, ovo je GNF oblik za gramatiku G.