GNF sta per forma normale di Greibach. Una CFG (grammatica libera dal contesto) è in GNF (forma normale di Greibach) se tutte le regole di produzione soddisfano una delle seguenti condizioni:
- Un simbolo iniziale che genera ε. Ad esempio, S → ε.
- Un non terminale che genera un terminale. Ad esempio, A → a.
- Un non terminale che genera un terminale seguito da un numero qualsiasi di non terminali. Ad esempio, S → aASB.
Per esempio:
G1 = aB, A → aA G2 = S → aAB
Le regole di produzione della Grammatica G1 soddisfano le regole specificate per GNF, quindi la grammatica G1 è in GNF. Tuttavia, la regola di produzione della Grammatica G2 non soddisfa le regole specificate per GNF poiché A → ε e B → ε contiene ε (solo il simbolo iniziale può generare ε). Quindi la grammatica G2 non è in GNF.
Passaggi per convertire CFG in GNF
Passo 1: Converti la grammatica in CNF.
Se la grammatica data non è in CNF, convertila in CNF. È possibile fare riferimento al seguente argomento per convertire il CFG in CNF: forma normale di Chomsky
Passo 2: Se la grammatica esiste la ricorsione a sinistra, eliminala.
Se la grammatica libera dal contesto contiene la ricorsione a sinistra, eliminala. È possibile fare riferimento al seguente argomento per eliminare la ricorsione a sinistra: Ricorsione a sinistra
Passaggio 3: Nella grammatica, converti la regola di produzione data nella forma GNF.
Se qualche regola di produzione nella grammatica non è in formato GNF, convertila.
Esempio:
S → XB | AA A → a | SA B → b X → a
Soluzione:
Poiché la grammatica G data è già in CNF e non esiste ricorsione a sinistra, possiamo saltare il passaggio 1 e il passaggio 2 e andare direttamente al passaggio 3.
La regola di produzione A → SA non è in GNF, quindi sostituiamo S → XB | AA nella regola di produzione A → SA come:
S → XB | AA A → a | XBA | AAA B → b X → a
La regola di produzione S → XB e B → XBA non è in GNF, quindi sostituiamo X → a nella regola di produzione S → XB e B → XBA come:
S → aB | AA A → a | aBA | AAA B → b X → a
Ora rimuoveremo la ricorsione a sinistra (A → AAA), otteniamo:
come controllare i numeri bloccati su Android
S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a
Ora rimuoviamo la produzione nulla C → ε, otteniamo:
S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a
La regola di produzione S → AA non è in GNF, quindi sostituiamo A → aC | aBAC | un | aBA nella regola di produzione S → AA come:
S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a
La regola di produzione C → AAC non è in GNF, quindi sostituiamo A → aC | aBAC | un | aBA nella regola di produzione C → AAC come:
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
Quindi, questa è la forma GNF per la grammatica G.