logo

Forma normale di Greibach (GNF)

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.