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 a{A}_1{A}_2\cdots A_n$

ou

$S\to \epsilon$

où $A$ est une variable, $a$ est une lettre, et $A_1{A}_2\dots 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 \epsilon$, 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

Modèle:Article détaillé On peut supposer que l'axiome de la grammaire ne figure pas dans un membre droit de règle.

Une règle $A\to \epsilon$, 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é

Modèle:Article détaillé 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,\dots ,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\to A_i{\alpha }_1\mid \dots \mid A_i{\alpha }_n\mid {\beta }_1\mid \dots \mid {\beta }_m$

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

$A_i\to {\beta }_{1}A{\text{'}}_i\mid \dots \mid {\beta }_{m}A{\text{'}}_i\mid {\beta }_1\mid \dots \mid {\beta }_m$

$A{\text{'}}_i\to {\alpha }_{1}A{\text{'}}_i\mid \dots \mid {\alpha }_{n}A{\text{'}}_i\mid {\alpha }_1\mid \dots \mid {\alpha }_n$

2. Suppression des occurrences de $A_i$ en tête : les occurrences de variables $A_j(1\le j\le 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 a{A}^{\prime }\mid a,A^{\prime }\to B{A}^{\prime }\mid B$.

On obtient :

Grammaire G₁ :

$A\to a{A}^{\prime }\mid a$

$A^{\prime }\to B{A}^{\prime }\mid B$

$B\to BC\mid b$

$C\to CA\mid c$

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

$B\to b{B}^{\prime }\mid b,B^{\prime }\to C{B}^{\prime }\mid C$, et les occurrences en tête de $B$

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

Grammaire G₂ :

$A\to a{A}^{\prime }\mid a$

$A^{\prime }\to b{B}^{\prime }{A}^{\prime }\mid b{A}^{\prime }\mid b{B}^{\prime }\mid b$

$B\to b{B}^{\prime }\mid b$

$B^{\prime }\to C{B}^{\prime }\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 c{C}^{\prime }\mid c,C^{\prime }\to A{C}^{\prime }\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 a{A}^{\prime }\mid a$

$A^{\prime }\to b{B}^{\prime }{A}^{\prime }\mid b{A}^{\prime }\mid b{B}^{\prime }\mid b$

$B\to b{B}^{\prime }\mid b$

$B^{\prime }\to c{C}^{\prime }{B}^{\prime }\mid c{B}^{\prime }\mid c{C}^{\prime }\mid c$

$C\to c{C}^{\prime }\mid c$

$C^{\prime }\to a{A}^{\prime }{C}^{\prime }\mid a{C}^{\prime }\mid a{A}^{\prime }\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,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,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 $\mathrm{\Sigma }\cup \mathrm{\Sigma }{V}^{*}\mathrm{\Sigma }$, où $\mathrm{\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 $\mathrm{\Sigma }\cup \mathrm{\Sigma }(\epsilon \cup V\cup V^2)\mathrm{\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 HotzModèle:,.

Autres constructions

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

• Modèle:Ouvrage Modèle:Commentaire biblio SRL.
• Modèle:Ouvrage
• Modèle:Introduction to Automata Theory, Languages, and Computation
• Modèle:Ouvrage — page 277.
• Modèle:Ouvrage.
• Modèle:Ouvrage Modèle:Commentaire biblio SRL.
• Modèle:Ouvrage Modèle:Commentaire biblio SRL.

Cours

• Modèle:Lien web.
• Modèle:Lien web.
• Modèle:Lien web.

Article récent

• Modèle:Article.

Voir aussi

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