GNF significa la forma normal de Greibach. Una CFG (gramàtica lliure de context) està en GNF (forma normal de Greibach) si totes les regles de producció compleixen una de les condicions següents:
- Un símbol d'inici que genera ε. Per exemple, S → ε.
- Un no terminal que genera un terminal. Per exemple, A → a.
- Un no terminal que genera un terminal que va seguit de qualsevol nombre de no terminals. Per exemple, S → aASB.
Per exemple:
listnode java
G1 = aB, A → aA G2 = S → aAB
Les regles de producció de la gramàtica G1 compleixen les regles especificades per a GNF, de manera que la gramàtica G1 està en GNF. Tanmateix, la regla de producció de la gramàtica G2 no compleix les regles especificades per a GNF ja que A → ε i B → ε conté ε (només el símbol d'inici pot generar ε). Per tant, la gramàtica G2 no està en GNF.
Passos per convertir CFG en GNF
Pas 1: Converteix la gramàtica a CNF.
Si la gramàtica donada no està en CNF, convertiu-la en CNF. Podeu consultar el tema següent per convertir el CFG a CNF: forma normal de Chomsky
Pas 2: Si la gramàtica existeix recursivitat a l'esquerra, elimineu-la.
Si la gramàtica lliure de context conté recursivitat esquerra, elimineu-la. Podeu consultar el tema següent per eliminar la recursivitat esquerra: Recurs esquerra
és una relació
Pas 3: A la gramàtica, convertiu la regla de producció donada a la forma GNF.
Si alguna regla de producció de la gramàtica no està en forma GNF, convertiu-la.
Exemple:
S → XB | AA A → a | SA B → b X → a
Solució:
Com que la gramàtica G donada ja està a CNF i no hi ha recursivitat esquerra, podem saltar el pas 1 i el pas 2 i anar directament al pas 3.
La regla de producció A → SA no està en GNF, així que substituïm S → XB | AA a la regla de producció A → SA com:
llista java de
S → XB | AA A → a | XBA | AAA B → b X → a
La regla de producció S → XB i B → XBA no està a GNF, per tant substituïm X → a a la regla de producció S → XB i B → XBA com:
S → aB | AA A → a | aBA | AAA B → b X → a
Ara eliminarem la recursió esquerra (A → AAA), obtenim:
S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a
Ara eliminarem la producció nul·la C → ε, obtenim:
numerar l'alfabet
S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a
La regla de producció S → AA no està en GNF, així que substituïm A → aC | aBAC | a | aBA a la regla de producció S → AA com:
S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a
La regla de producció C → AAC no està en GNF, així que substituïm A → aC | aBAC | a | aBA a la regla de producció C → AAC com:
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
Per tant, aquesta és la forma GNF per a la gramàtica G.