Forme normale de Greibach

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, et notamment en théorie des langages formels, une grammaire algébrique est en forme normale de Greibach 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[modifier | modifier le code]

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

ou

est une variable, est une lettre, et est une suite éventuellement vide de variables ; 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 , l'algorithme est plus simple ; il existe des transformations complexité en temps dans le cas général et en temps si la grammaire n'a pas de règle unité (de la forme pour une variable )[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.

Construction[modifier | modifier le code]

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[modifier | modifier le code]

Article détaillé : Élimination des ε-règles

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

Une règle , où n'est pas l'axiome, est supprimée ; on considère chaque règle figure dans , et on ajoute, pour chaque occurrence , la règle à la grammaire, sauf si on crée une epsilon-règle. Par exemple, si

on ajoute les trois règles

.

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

Deuxième phase : suppression des règles unité[modifier | modifier le code]

Article détaillé : Suppression des règles unité

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

pour chaque règle

(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 ) par l'identification des variables d'un cycle : elles sont toutes remplacées par l'une d'entre elles.

Mise sous forme normale[modifier | modifier le code]

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

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

où les ne commencent pas par sont remplacées par

2. Suppression des occurrences de en tête : les occurrences de variables 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 , une pour chaque lettre , avec la règle .

Exemple[modifier | modifier le code]

Voici un exemple tiré du livre d'Olivier Carton[6] (on écrit au lieu de ) :

Grammaire G0 :

Les deux règles de sont remplacées par

.

On obtient :

Grammaire G1 :

Les deux règles de sont remplacées par

, et les occurrences en tête de

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

Grammaire G2 :

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

,

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

Grammaire G3

Autres formes normales[modifier | modifier le code]

Forme normale quadratique[modifier | modifier le code]

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

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 :

du langage de Lukasiewicz sont sous forme quadratique, la grammaire

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

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 , ce qui donne , d'où

.

Forme normale bilatère[modifier | modifier le code]

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 , où et 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 , 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].

Autres constructions[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. Hopcroft et Ullman 1979, p. 95.
  2. (en) Sheila A. Greibach, « A New Normal-Form Theorem for Context-Free Phrase Structure Grammars », Journal of the ACM, vol. 12, no 1,‎ , p. 42–52 (DOI 10.1145/321250.321254).
  3. (en) Norbert Blum et Robert Koch, « Greibach Normal Form Transformation Revisited », Information and Computation, vol. 150, no 1,‎ , p. 112–118 (DOI 10.1006/inco.1998.2772, lire en ligne).
  4. On introduit, comme pour la construction de la Forme normale de Chomsky, une nouvelle variable qui devient l'axiome, et une unique règle supplémentaire , où est l'ancien axiome.
  5. Hopcroft, Motwani et Ullman 2007, p. 268.
  6. a et b Carton 2008.
  7. Günter Hotz, « Normal form transformations of context-free grammars », Acta Cybernetica, no 1,‎ , p. 65-84.
  8. (en) Joost Engelfriet, « An elementary proof of double Greibach normal form », Information Processing Letters, vol. 44, no 6,‎ , p. 291–293 (DOI 10.1016/0020-0190(92)90101-Z).
  9. Daniel J. Rosenkrantz, « Matrix equations and normal forms for context-free grammars », Journal of the ACM, vol. 14, no 3,‎ , p. 501–507.
  10. (en) Ryo Yoshinaka, « An elementary proof of a generalization of double Greibach normal form », Information Processing Letters, vol. 109, no 10,‎ , p. 490–492 (DOI 10.1016/j.ipl.2009.01.015).

Bibliographie[modifier | modifier le code]

Manuels
Cours

Voir aussi[modifier | modifier le code]