GNF signifie Forme normale de Greibach. Une CFG (context free grammar) est au format GNF (forme normale de Greibach) si toutes les règles de production satisfont à l'une des conditions suivantes :

• Un symbole de départ générant ε. Par exemple, S → ε.
• Un non-terminal générant un terminal. Par exemple, A → a.
• Un non-terminal générant un terminal qui est suivi par un nombre quelconque de non-terminaux. Par exemple, S → aASB.

Par exemple:

 G1 = aB, A → aA G2 = S → aAB 

Les règles de production de la grammaire G1 satisfont aux règles spécifiées pour GNF, donc la grammaire G1 est en GNF. Cependant, la règle de production de la grammaire G2 ne satisfait pas aux règles spécifiées pour GNF car A → ε et B → ε contiennent ε (seul le symbole de début peut générer ε). La grammaire G2 n’est donc pas en GNF.

Étapes pour convertir CFG en GNF

Étape 1: Convertissez la grammaire en CNF.

Si la grammaire donnée n'est pas en CNF, convertissez-la en CNF. Vous pouvez vous référer au sujet suivant pour convertir le CFG en CNF : Forme normale de Chomsky

Étape 2: Si la grammaire existe par récursion gauche, éliminez-la.

Si la grammaire sans contexte contient une récursion gauche, éliminez-la. Vous pouvez vous référer à la rubrique suivante pour éliminer la récursion gauche : Récursion gauche

Étape 3: Dans la grammaire, convertissez la règle de production donnée sous forme GNF.

Si une règle de production dans la grammaire n'est pas sous forme GNF, convertissez-la.

Exemple:

 S → XB | AA A → a | SA B → b X → a 

Solution:

Comme la grammaire G donnée est déjà en CNF et qu'il n'y a pas de récursion gauche, nous pouvons donc sauter l'étape 1 et l'étape 2 et passer directement à l'étape 3.

La règle de production A → SA n'est pas dans GNF, on substitue donc S → XB | AA dans la règle de production A → SA comme :

 S → XB | AA A → a | XBA | AAA B → b X → a 

La règle de production S → XB et B → XBA n'est pas dans GNF, nous substituons donc X → a dans la règle de production S → XB et B → XBA comme :

 S → aB | AA A → a | aBA | AAA B → b X → a 

Nous allons maintenant supprimer la récursion gauche (A → AAA), nous obtenons :

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Nous allons maintenant supprimer la production nulle C → ε, nous obtenons :

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

La règle de production S → AA n'est pas dans GNF, on substitue donc A → aC | aBAC | un | aBA dans la règle de production S → AA comme :

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

La règle de production C → AAC n'est pas dans GNF, on substitue donc A → aC | aBAC | un | aBA dans la règle de production C → AAC comme :

 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 

Il s’agit donc de la forme GNF de la grammaire G.