Pour les articles homonymes, voir GNF.

En informatique théorique, et notamment en théorie des langages formels, une grammaire algébrique est en forme normale de Greibach (en anglais, Greibach normal form ou GNF) si les membres droits de ses règles commencent tous par un symbole terminal, suivi éventuellement d'une ou plusieurs variables. Une variante permet une règle additionnelle pour engendrer le mot vide s'il fait partie du langage. Cette forme normale porte le nom de Sheila Greibach qui l'a introduite et a prouvé son existence.

D'autres formes normales de grammaire existent, comme la forme normale de Chomsky, ou les grammaires sans récursivité gauche. La forme normale de Greibach est la plus élaborée de ces formes normales, et elle a été raffinée par la suite.

Une grammaire algébrique est en forme normale de Greibach si toutes ses règles sont de la forme :

${\displaystyle A\to aA_{1}A_{2}\cdots A_{n}}$

ou

${\displaystyle S\to \varepsilon }$

où ${\displaystyle A}$ est une variable, ${\displaystyle a}$ est une lettre, et ${\displaystyle A_{1}A_{2}\ldots A_{n}}$ est une suite éventuellement vide de variables ; ${\displaystyle S}$ est l'axiome et ε est le mot vide^[1].

Une grammaire en forme normale de Greibach est notamment sans récursivité gauche. La propriété principale est que toute grammaire algébrique peut être transformée en une grammaire équivalent en forme normale de Greibach, théorème établi en 1965 par Sheila Greibach^[2].

Il existe plusieurs constructions. Lorsqu'il n'y a pas de epsilon-règle ${\displaystyle S\to \varepsilon }$, l'algorithme est plus simple ; il existe des transformations complexité en temps ${\displaystyle O(n^{4})}$ dans le cas général et en temps ${\displaystyle O(n^{3})}$ si la grammaire n'a pas de règle unité (de la forme ${\displaystyle A\to B}$ pour une variable ${\displaystyle B}$)^[3].

En forme normale de Greibach, une dérivation engendre, à chaque pas de dérivation, une lettre d'un mot du langage donnée : la longueur de la dérivation est donc égale à la longueur du mot. La forme normale peut être utilisée, de manière équivalente, pour construire une automate à pile qui accepte les mots du langage en temps réel, c'est-à-dire qui lit une lettre du mot d'entrée à chaque pas de calcul.

La construction d'une grammaire en forme normale de Greibach à partir d'une grammaire algébrique donnée par partie des sujets traités dans de nombreux manuels d'informatique théorique sur les langages formels, les automates et leur complexité. Une des constructions est en plusieurs phases :

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].

Un autre construction, plus algébrique, a été proposée par Daniel J. Rosenkrantz^[9],[6]. Elle repose sur la résolution d'un système d'équations dans l'algèbre des parties sur un monoïde libre. Cette méthode conduit directement à une grammaire quadratique si on part d'une grammaire sous forme normale de Chomsky. D'autres constructions, et des généralisations, ont été données par divers auteurs^[10].

Manuels

• Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, lire en ligne) — Section 2.5 Forme normale Greibach.
• John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Addison Wesley, 2007, 3^e éd., xvii+535 (ISBN 978-0-321-45536-9 et 0-321-45536-3) — page 277.
• (en) Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Learning, 2001, 410 p. (ISBN 978-0-7637-1422-2 et 0763714224, lire en ligne).
• (de) Katrin Erk et Lutz Priese, Theoretische Informatik : eine umfassende Einführung, Berlin, Springer, 2008, 485 p. (ISBN 978-3-540-76319-2, OCLC 244015158) — 6.8.1 6.3 Chomsky- und Greibach-Normalform p. 121.
• (en) Michael A. Harrison, Introduction to Formal Language Theory, Reading, Mass. u.a., Addison-Wesley, 1978, 594 p. (ISBN 0-201-02955-3, OCLC 266962302) — Section 4.6 Greibach normal form, p. 111-120.

Cours

• Arthur Milchior, « Forme normale de Greibach », Rédactions cours ENS (Olivier Carton), 19 décembre 2008.
• Jacques Désarménien, « Chapitre 4.4 La forme normale de Greibach », Cours automates, Université Paris-Est Marne-la-Vallée.
• Sandrine Julia, « Cours 7 - Grammaires hors contexte (suite) », Automates & Langages, Université de Nice - Sophia Antipolis.

Article récent

• Manfred Droste, Sven Dziadek et Werner Kuich, « Greibach normal form for ω-algebraic systems and weighted simple ω-pushdown automata », Information and Computation, vol. 285, Part B, n^o 104871,‎ 2022 (arXiv 2007.08866).

• Forme de Backus-Naur
• Forme normale de Chomsky
• Forme normale de Kuroda

• Portail de l'informatique théorique
• Portail des mathématiques