Forma normale di Greibach
Un CFG è in Greibach Normal Form se le Produzioni sono nelle seguenti forme:
A → b
A → bD 1 … D n
S → ε
dove A, D 1 , ...., D n sono non terminali eb è un terminale.
Algoritmo per convertire un CFG nella forma normale di Greibach
Step 1 - Se il simbolo di avvio S si verifica su un lato destro, crea un nuovo simbolo di inizio S’ e una nuova produzione S’ → S.
Step 2- Rimuovi le produzioni Null. (Utilizzo dell'algoritmo di rimozione della produzione Null discusso in precedenza)
Step 3- Rimuovere le produzioni unitarie. (Utilizzo dell'algoritmo di rimozione della produzione unitaria discusso in precedenza)
Step 4 - Rimuovi tutta la ricorsione a sinistra diretta e indiretta.
Step 5 - Effettua opportune sostituzioni delle produzioni per convertirle nella forma corretta di GNF.
Problema
Converti il seguente CFG in CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
Soluzione
Qui, Snon viene visualizzato a destra di alcuna produzione e non sono presenti produzioni unitarie o nulle nel set di regole di produzione. Quindi, possiamo saltare dal Passaggio 1 al Passaggio 3.
Step 4
Ora dopo la sostituzione
X in S → XY | Xo | p
con
mX | m
otteniamo
S → mXY | mio | mXo | mo | p.
E dopo la sostituzione
X in Y → X n | o
con il lato destro di
X → mX | m
otteniamo
Y → mXn | mn | o.
Due nuove produzioni O → o e P → p vengono aggiunte al set di produzione e quindi siamo arrivati alla GNF finale come segue:
S → mXY | mio | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O → o
P → p