Forme normale de Greibach

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.

Description

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

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

ou

$S\to \varepsilon$

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

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.

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

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.

Construction

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 :

Phase préliminaire : suppression des epsilon-règles

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

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

$B\to aAbAc$

on ajoute les trois règles

$B\to abAc,B\to aAbc,B\to abc$.

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

Deuxième phase : suppression des règles unité

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

$A\to \alpha$

pour chaque règle

$B\to \alpha$

(sauf si c'est une règle unité précédemment enlevée). Cette technique est complétée dans le cas de cycles (comme l'existence de trois règles $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.

Mise sous forme normale

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

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

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

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

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

$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 $A_{i}$ en tête : les occurrences de variables $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 $T_{a}$, une pour chaque lettre $a$, avec la règle $T_{a}\to a$.

Exemple

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

Grammaire G₀ :

$A\to AB\mid a$

$B\to BC\mid b$

$C\to CA\mid c$

Les deux règles de $A$ sont remplacées par

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

On obtient :

Grammaire G₁ :

$A\to aA'\mid a$

$A'\to BA'\mid B$

$B\to BC\mid b$

$C\to CA\mid c$

Les deux règles de $B$ sont remplacées par

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

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

Grammaire G₂ :

$A\to aA'\mid a$

$A'\to bB'A'\mid bA'\mid bB'\mid b$

$B\to bB'\mid b$

$B'\to CB'\mid C$

$C\to CA\mid c$

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

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

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

Grammaire G₃

$A\to aA'\mid a$

$A'\to bB'A'\mid bA'\mid bB'\mid b$

$B\to bB'\mid b$

$B'\to cC'B'\mid cB'\mid cC'\mid c$

$C\to cC'\mid c$

$C'\to aA'C'\mid aC'\mid aA'\mid a$

Autres formes normales

Forme normale quadratique

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

$A\to aV$

où $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 :

$S\to aSS|b$

du langage de Lukasiewicz sont sous forme quadratique, la grammaire

$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 $T$ et on remplace la grammaire par :

$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 $T$, ce qui donne $T\to aSSSS\mid bS$, d'où

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

Forme normale bilatère

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 $\Sigma \cup \Sigma V^{*}\Sigma$, où $\Sigma$ et $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 $\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.

Autres constructions

Un autre construction, plus algébrique, a été proposée par Daniel J. Rosenkrantz. 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.

Bibliographie

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

Voir aussi

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