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.