Forme normale de Greibach

On peut supposer que l'axiome de la grammaire ne figure pas dans un membre droit de règle[4].

Une règle ${\displaystyle A\to \varepsilon }$, où ${\displaystyle A}$ n'est pas l'axiome, est supprimée ; on considère chaque règle ${\displaystyle B\to \alpha }$ où ${\displaystyle A}$ figure dans ${\displaystyle \alpha }$, et on ajoute, pour chaque occurrence ${\displaystyle \alpha =\beta A\gamma }$, la règle ${\displaystyle B\to \beta \gamma }$ à la grammaire, sauf si on crée une epsilon-règle. Par exemple, si

${\displaystyle B\to aAbAc}$

on ajoute les trois règles

${\displaystyle B\to abAc,B\to aAbc,B\to abc}$.

Un règle dont le membre droit contient ${\displaystyle n}$ variables qui toutes dérivent en le mot vide peut ainsi donner jusqu'à ${\displaystyle 2^{n}}$ nouvelles règles.

Une règle unité est une règle de la forme ${\displaystyle A\to B}$, où ${\displaystyle B}$ est une variable. Pour éliminer ce type de règles, on remplace une telle règle par la règle

${\displaystyle A\to \alpha }$

pour chaque règle

${\displaystyle B\to \alpha }$

(sauf si c'est une règle unité précédemment enlevée[5]). Cette technique est complétée dans le cas de cycles (comme l'existence de trois règles ${\displaystyle A\to B,B\to C,C\to A}$) par l'identification des variables d'un cycle : elles sont toutes remplacées par l'une d'entre elles.

On suppose la grammaire sans ε-règles et sans règles unité. On suppose les variables numérotées en ${\displaystyle A_{1},A_{2},\dots ,A_{m}}$ ; on définit une suite ${\displaystyle G_{0},G_{1},\dots ,G_{n}}$ de grammaires, où ${\displaystyle G_{0}}$ est la grammaire initiale, avec la propriété que dans ${\displaystyle G_{i}}$, les variables ${\displaystyle A_{1},\ldots ,A_{i}}$ n'apparaissent pas en tête des membres droits de règle. On suppose la grammaire ${\displaystyle G_{i-1}}$ construite, et on procède en deux étapes

1. Suppression de la récursivité gauche pour ${\displaystyle A_{i}}$ : on supprime les ${\displaystyle A_{i}}$ en tête des règles de ${\displaystyle A_{i}}$ : les règles

${\displaystyle A_{i}\rightarrow A_{i}\alpha _{1}\mid \ldots \mid A_{i}\alpha _{n}\mid \beta _{1}\mid \ldots \mid \beta _{m}}$

où les ${\displaystyle \beta _{j}}$ ne commencent pas par ${\displaystyle A}$ sont remplacées par

${\displaystyle A_{i}\rightarrow \beta _{1}A'_{i}\mid \ldots \mid \beta _{m}A'_{i}\mid \beta _{1}\mid \ldots \mid \beta _{m}}$

${\displaystyle A'_{i}\rightarrow \alpha _{1}A'_{i}\mid \ldots \mid \alpha _{n}A'_{i}\mid \alpha _{1}\mid \ldots \mid \alpha _{n}}$

2. Suppression des occurrences de ${\displaystyle A_{i}}$ en tête : les occurrences de variables ${\displaystyle A_{j}(1\leq j\leq i)}$ qui figurent ou peuvent apparaître en tête dans les membres droits de règles sont remplacées par l'ensemble des règles de ces variables.

Si, à la fin, il reste des lettres terminales dans les membres droits de règles autrement qu'en tête, on les remplace par une variable additionnelle ${\displaystyle T_{a}}$, une pour chaque lettre ${\displaystyle a}$, avec la règle ${\displaystyle T_{a}\to a}$.

Voici un exemple tiré du livre d'Olivier Carton[6] (on écrit ${\displaystyle A,B,C}$ au lieu de ${\displaystyle A_{1},A_{2},A_{3}}$) :

Grammaire G₀ :

${\displaystyle A\to AB\mid a}$

${\displaystyle B\to BC\mid b}$

${\displaystyle C\to CA\mid c}$

Les deux règles de ${\displaystyle A}$ sont remplacées par

${\displaystyle A\to aA'\mid a,\quad A'\to BA'\mid B}$.

On obtient :

Grammaire G₁ :

${\displaystyle A\to aA'\mid a}$

${\displaystyle A'\to BA'\mid B}$

${\displaystyle B\to BC\mid b}$

${\displaystyle C\to CA\mid c}$

Les deux règles de ${\displaystyle B}$ sont remplacées par

${\displaystyle B\to bB'\mid b,\quad B'\to CB'\mid C}$, et les occurrences en tête de ${\displaystyle B}$

sont remplacées par ces deux règles. On obtient :

Grammaire G₂ :

${\displaystyle A\to aA'\mid a}$

${\displaystyle A'\to bB'A'\mid bA'\mid bB'\mid b}$

${\displaystyle B\to bB'\mid b}$

${\displaystyle B'\to CB'\mid C}$

${\displaystyle C\to CA\mid c}$

De même, les deux règles de ${\displaystyle C}$ sont remplacées par, dans une première étape, par

${\displaystyle C\to cC'\mid c,\quad C'\to AC'\mid A}$,

mais la variable ${\displaystyle A}$ en tête est remplacée par ses règles, de même que la variable ${\displaystyle C}$ en tête. On obtient la grammaire :

Grammaire G₃

${\displaystyle A\to aA'\mid a}$

${\displaystyle A'\to bB'A'\mid bA'\mid bB'\mid b}$

${\displaystyle B\to bB'\mid b}$

${\displaystyle B'\to cC'B'\mid cB'\mid cC'\mid c}$

${\displaystyle C\to cC'\mid c}$

${\displaystyle C'\to aA'C'\mid aC'\mid aA'\mid a}$

Un grammaire est sous forme normale quadratique de Greibach si toutes ses règles sont de la forme

${\displaystyle A\to aV}$

où ${\displaystyle V}$ est composé d'au plus deux variables, donc si de plus les membres droits de règles sont de longueur au plus 3. La grammaire ci-dessus, et la grammaire :

${\displaystyle S\to aSS|b}$

du langage de Lukasiewicz sont sous forme quadratique, la grammaire

${\displaystyle S\to aSSS|b}$

ne l'est pas. On peut la transformer en grammaire quadratique en groupant les occurrences consécutive ; ici, on introduit une nouvelle variable ${\displaystyle T}$ et on remplace la grammaire par :

${\displaystyle S\to aST|b,\quad T\to SS}$

La grammaire n'est plus sous forme normale de Greibach, mais comme précédemment, on remplace la variable de tête dans la règle pour ${\displaystyle T}$, ce qui donne ${\displaystyle T\to aSSSS\mid bS}$, d'où

${\displaystyle S\to aST|b,\quad T\to aTT\mid bS}$.

Un grammaire est sous forme normale bilatère ou forme normale double de Greibach si toutes ses règles débutent et finissent par une lettre terminale, formellement si les membres droits de règles sont dans ${\displaystyle \Sigma \cup \Sigma V^{*}\Sigma }$, où ${\displaystyle \Sigma }$ et ${\displaystyle V}$ sont l'alphabet terminal et non terminal de la grammaire. Une grammaire est sous forme normale bilatère quadratique si les membres droits de règles sont dans ${\displaystyle \Sigma \cup \Sigma (\varepsilon \cup V\cup V^{2})\Sigma }$, donc si de plus les membres droits des règles sont de longueur inférieure ou égale à 4. Cette construction a été introduite par Günter Hotz[7] - [8].