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 ₁ … D _n

S → ε

où A, D ₁ , ...., 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