GNF înseamnă forma normală Greibach. O CFG (gramatică fără context) este în GNF (forma normală Greibach) dacă toate regulile de producție îndeplinesc una dintre următoarele condiții:

• Un simbol de pornire care generează ε. De exemplu, S → ε.
• Un non-terminal care generează un terminal. De exemplu, A → a.
• Un non-terminal care generează un terminal care este urmat de orice număr de non-terminale. De exemplu, S → aASB.

De exemplu:

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

Regulile de producție ale gramaticii G1 îndeplinesc regulile specificate pentru GNF, deci gramatica G1 este în GNF. Totuși, regula de producție a gramaticii G2 nu îndeplinește regulile specificate pentru GNF, deoarece A → ε și B → ε conține ε (doar simbolul de început poate genera ε). Deci gramatica G2 nu este în GNF.

Pași pentru conversia CFG în GNF

Pasul 1: Convertiți gramatica în CNF.

Dacă gramatica dată nu este în CNF, convertiți-o în CNF. Puteți face referire la următorul subiect pentru a converti CFG în CNF: forma normală Chomsky

Pasul 2: Dacă gramatica există recursivitate stângă, eliminați-o.

Dacă gramatica fără context conține recursiunea stângă, eliminați-o. Puteți consulta următorul subiect pentru a elimina recursiunea stângă: Recursie stânga

Pasul 3: În gramatică, convertiți regula de producție dată în forma GNF.

Dacă vreo regulă de producție din gramatică nu este în formă GNF, convertiți-o.

Exemplu:

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

Soluţie:

Deoarece gramatica dată G este deja în CNF și nu există recursivitate stângă, așa că putem sări peste pasul 1 și pasul 2 și să mergem direct la pasul 3.

Regula de producție A → SA nu este în GNF, așa că înlocuim S → XB | AA în regula de producție A → SA ca:

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

Regula de producție S → XB și B → XBA nu este în GNF, așa că înlocuim X → a în regula de producție S → XB și B → XBA ca:

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

Acum vom elimina recursiunea stângă (A → AAA), obținem:

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

Acum vom elimina producția nulă C → ε, obținem:

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

Regula de producție S → AA nu este în GNF, așa că înlocuim A → aC | aBAC | a | aBA în regula de producție S → AA ca:

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

Regula de producție C → AAC nu este în GNF, așa că înlocuim A → aC | aBAC | a | aBA în regula de producție C → AAC ca:

 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 

Prin urmare, aceasta este forma GNF pentru gramatica G.