Forme normale de Greibach
Un CFG est dans la forme normale de Greibach si les productions sont dans les formes suivantes -
A → b
A → bD 1 … D n
S → ε
où A, D 1 , ...., D n sont des non-terminaux et b est un terminal.
Algorithme pour convertir un CFG en forme normale de Greibach
Step 1 - Si le symbole de départ S se produit sur un côté droit, créez un nouveau symbole de départ S’ et une nouvelle production S’ → S.
Step 2- Supprimer les productions nulles. (Utilisation de l'algorithme de suppression de production Null discuté précédemment)
Step 3- Supprimer les productions unitaires. (Utilisation de l'algorithme de suppression de production d'unité discuté précédemment)
Step 4 - Supprimer toutes les récursions à gauche directes et indirectes.
Step 5 - Faire des substitutions appropriées de productions pour les convertir en la forme appropriée de GNF.
Problème
Convertissez le CFG suivant en CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
Solution
Ici, Sn'apparaît sur le côté droit d'aucune production et il n'y a pas de productions unitaires ou nulles dans l'ensemble de règles de production. Nous pouvons donc passer de l'étape 1 à l'étape 3.
Step 4
Maintenant après avoir remplacé
X dans S → XY | Xo | p
avec
mX | m
on obtient
S → mXY | mY | mXo | mo | p.
Et après avoir remplacé
X dans Y → X n | o
avec le côté droit de
X → mX | m
on obtient
Y → mXn | mn | o.
Deux nouvelles productions O → o et P → p sont ajoutées à l'ensemble de production, puis nous sommes arrivés au GNF final comme suit -
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O → o
P → p