Forme normale de Chomsky

En informatique théorique, et notamment en théorie des langages, une grammaire non contextuelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme :

1. X → Y Z {\displaystyle X\to YZ}  ;
2. ou X → a {\displaystyle X\to a}  ;
3. ou S → ε {\displaystyle S\to \varepsilon }

où X , Y , Z {\displaystyle X,Y,Z} sont des symboles non terminaux, a {\displaystyle a} est un symbole terminal, S {\displaystyle S} est l'axiome de la grammaire, et ε {\displaystyle \varepsilon } est le mot vide.

Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.

La forme normale de Chomsky tient son nom du linguiste américain Noam Chomsky, qui a conçu également la hiérarchie qui porte son nom, et qui a décrit cette forme normale à cette occasion dans un article publié en 1959^[1].

Une variante de la définition consiste à ne pas permettre le mot vide : seules des règles de la forme

X → Y Z {\displaystyle X\to YZ} ou X → a {\displaystyle X\to a} ,

sont permises où X {\displaystyle X} , Y {\displaystyle Y} et Z {\displaystyle Z} sont des symboles non terminaux et a {\displaystyle a} est un symbole terminal. C'est la définition adoptée par exemple par Carton^[2] ou Hopcroft et. al. ^[3]. Bien entendu, ces grammaires n'engendrent pas le mot vide.

Une autre variante^[4],[5] demande que les membres droits de règles soient de longueur au plus 2, mais n'impose pas que les membres droits de longueur 2 soient formés exclusivement de symboles non terminaux. Une telle grammaire est appelée 2-forme normale ou « 2NF ».

Toute grammaire écrite en forme normale de Chomsky est une grammaire non contextuelle. Inversement, toute grammaire hors contexte peut être transformée en une grammaire équivalente (c'est-à-dire engendrant le même langage) en forme normale de Chomsky.

À l'exception de la règle (3), toutes les règles d'une grammaire sous forme normale de Chomsky sont croissantes ; par conséquent, tout au long d'une dérivation, les longueurs des mots croissent. Ils croissent de 1 avec une règle de type (1), et restent de même longueur avec une règle de type (2). La dérivation d'un mot de longueur n > 0 {\displaystyle n>0} se fait donc toujours en 2 n − 1 {\displaystyle 2n-1} étapes : il y a n − 1 {\displaystyle n-1} étapes de type (1) et n {\displaystyle n} étapes de type (2). De plus, dans la mesure où toutes les règles de dérivation de non-terminaux transforment un non-terminal en deux non-terminaux, un arbre de dérivation fondé sur une grammaire en forme normale de Chomsky est un arbre binaire avec 2 n − 1 {\displaystyle 2n-1} nœuds internes et n {\displaystyle n} feuilles, et sa hauteur est au maximum la longueur de la chaîne de caractères.

Grâce à ces propriétés, de nombreuses preuves dans le domaine des langages formels deviennent plus simples en utilisant la forme normale de Chomsky (par exemple le fait que l'appartenance d'un mot au langage engendré est décidable). Plusieurs algorithmes généraux d'analyse syntaxique, comme l'algorithme de Cocke-Younger-Kasami, emploient cette forme normale.

La conversion d'une grammaire en forme normale de Chomsky se fait par une suite de transformations simples, appliquées dans un certain ordre. La plupart des manuels de théorie des automates décrivent cette conversion^{[6],[7],[8],[9], [10],[11] ,[12]}. Dans un article pédagogique, Lange et Leiß^[13] décrivent soigneusement ces opérations, et ils donnent des noms aux étapes de la transformation ce qui facilite l'exposition. De plus, ils indiquent l'ordre à utiliser qui permet de garantir une complexité linéaire.

En général, la transformation est précédée d'une opération — appelée « réduction » chez Carton 2008, (Section 2.1.2 : Grammaires réduites, p. 79) ou « eliminating useless symbols » chez Hopcroft, Motwani et Ullman 2007, (Section 7.1.1 : Eliminating useless symbols, p. 262) — qui sert à supprimer les variables inutiles. Une variable X est utile si elle figure dans une dérivation de l'axiome en un mot terminal; pour cela, elle doit être accessible à partir de l’axiome par une suite de dérivations, et être « coaccessible », au sens qu'elle doit pouvoir être dérivée en un mot terminal.

Chacune des cinq transformation suivantes (START, TERM, BIN, DEL, UNIT) établit une des propriétés requise par la forme normale de Chomsky. On les présente, en suivant Lange et Leiß, comme si elles s'appliquaient à une grammaire générale ; on verra plus loin que l'ordre d'application est important si on veut minimiser la complexité en temps. Dans ces ordres particuliers, certaines opérations sont plus simples, comme l'opération UNIT qui sert à éliminer les règles unité.

La complexité des opérations se mesure par rapport à la taille de la grammaire G donnée. Elle est définie simplement^[13] comme la place que prend l'écriture des règles, sont

| G | = ∑ X → α | X α | {\displaystyle |G|=\sum _{X\to \alpha }|X\alpha |}

où la sommation porte sur toutes les règles X → α {\displaystyle X\to \alpha } de la grammaire. En particulier, une ε-règle contribue pour 1 dans la somme.

Pour cela, on introduit un nouveau symbole S 0 {\displaystyle S_{0}} qui devient l'axiome, et la règle

S 0 → S {\displaystyle S_{0}\to S} ,

où S {\displaystyle S} est l’ancien axiome. Ceci ne modifie pas le langage engendré, et la variable S 0 {\displaystyle S_{0}} ne figure pas dans un membre droit de règle.

Si une lettre terminale a {\displaystyle a} figure dans un membre droit de règle de longueur au moins 2, on la remplace par une nouvelle N a {\displaystyle N_{a}} et on ajoute la nouvelle règle

N a → a {\displaystyle N_{a}\to a}

et on remplace la règle ci-dessus par

X → W N a T {\displaystyle X\to WN_{a}T}

En fait, on fait ce remplacement simultanément pour toutes les occurrences de lettres terminales dans les membres droits de règles. Cela ne modifie pas le langage engendré, et augmente le nombre de règles d'au plus le nombre de lettres terminales. L'opération est donc linéaire en fonction de |G|.

On remplace une règle

X → Y 1 Y 2 ⋯ Y n {\displaystyle X\to Y_{1}Y_{2}\cdots Y_{n}} ,

par les règles

X → Y 1 Z 1 ,   Z 1 → Y 2 Z 2 , … ,   Z n − 2 → Y n − 1 Y n {\displaystyle X\to Y_{1}Z_{1},\ Z_{1}\to Y_{2}Z_{2},\ldots ,\ Z_{n-2}\to Y_{n-1}Y_{n}} ,

où les Z i {\displaystyle Z_{i}} sont des nouveaux symboles non terminaux^[14],[15]. Cette opération au plus triple la taille de la grammaire.

Une ε-règle est une règle de la forme

X → ε {\displaystyle X\to \varepsilon } ,

où X {\displaystyle X} n'est pas l’axiome de la grammaire. On commence par déterminer les variables qui dérivent en ε ; ces variables, appelées annulables (« nullable » en anglais), se calculent par récurrence : X est annulable s'il existe une règle

X → Y 1 ⋯ Y n {\displaystyle X\to Y_{1}\cdots Y_{n}} telle que Y 1 , … , Y n {\displaystyle Y_{1},\ldots ,Y_{n}} sont tous annulables.

Pour toute variable X {\displaystyle X} , annulable ou non, toute règle

X → Y 1 ⋯ Y n {\displaystyle X\to Y_{1}\cdots Y_{n}}

est remplacée par toutes les règles obtenues en supprimant une ou plusieurs, voire toutes les variables annulables dans le membre droit de règle, puis on supprime toutes les ε-règles (à l'exception de celle de l'axiome si elle est présente)^[16].

Par exemple, dans la grammaire suivante avec axiome S₀,

S₀ → AbB | C

B → AA | AC

C → b | c

A → a | ε

La variable A, et par conséquent B, sont annulables, et ni C ni S₀ ne le sont. Dans la version intermédiaire suivante, on a coloré les variables à supprimer :

S₀ → AbB | AbB | AbB | AbB | C

B → AA | AA| AA | AεA | AC | AC

C → b | c

A → a | ε

Après suppression des variables en vert, et des règles A → ε (d'origine) et B → ε (produite), on obtient la grammaire

S₀ → AbB | Ab | bB | b | C

B → AA | A | AC | C

C → b | c

A → a

Cette grammaire engendre le même langage, sans ε-règles.

Une règle unité est une règle de la forme

X → Y {\displaystyle X\to Y}

où X {\displaystyle X} et Y {\displaystyle Y} sont des variables, et plus généralement une règle

X → W Y T {\displaystyle X\to WYT} ,

où toutes les variable de W T {\displaystyle WT} sont annulables. Pour éliminer ce type de règles, on la remplace par la règle

X → α {\displaystyle X\to \alpha }

pour chaque règle

Y → α {\displaystyle Y\to \alpha }

sauf si c'est une règle unité précédemment enlevée^[17]. Cette technique est complétée dans le cas de cycles (comme l'existence de trois règles X → Y , Y → Z , Z → X {\displaystyle X\to Y,Y\to Z,Z\to X} ) par l'identification des variables d'un cycle : elles sont toutes remplacées par l'une d'entre elles. La transformation UNIT peut faire passer la taille de la grammaire de |G| à |G|².

Préservation des propriétés des transformations
✓ la transformation X préserve le résultat de Y ✗ la transformation X peut altérer le résultat de Y.
X\Y	START	TERM	BIN	DEL	UNIT
START		✓	✓	✓	✗
TERM	✓		✗	✓	✓
BIN	✓	✓		✓	✓
DEL	✓	✓	✓		✗
UNIT	✓	✓	✓	(✓)*
*UNIT conserve le résultat de DEL si START a été effectué au préalable.

L'ordre dans lequel les opérations sont appliquées est important pour deux raisons : d'abord, il est possible qu'une transformation puisse annuler l'effet d'une opération précédente ; par exemple, si on utilise START après UNIT, on réintroduit une règle unité. Sur la table, les ordres convenables sont indiqués.

Une autre raison pour choisir l'ordre des opérations avec soin est l'augmentation possible de la taille de la grammaire, et par là même la complexité des opérations. La taille de la grammaire résultat peut aller de |G|² à 2^2|G| pour une grammaire de taille |G|^[18]. L'augmentation dépend de l'ordre entre DEL et BIN. Il peut être exponentiel si DEL est opéré en premier, puisqu'une règle dont le membre droit est de longueur n peut produire 2²ⁿ règles, et sinon est linéaire. UNIT peut provoquer une augmentation quadratique de la taille^[4].

La plus petite augmentation de taille se produit pour les ordres (START,TERM,BIN,DEL,UNIT) et (START,BIN,DEL,UNIT,TERM).

Les divers manuels et cours de théorie des langages contiennent en général, en plus de l'exposé des procédures, des démonstrations de la correction des algorithmes. Une formalisation de ces opérations de réduction, à savoir la suppression de variables inutiles, l’élimination des règles unité et des epsilon-règles dans l’assistant de preuve Rocq a été entreprise par Marcus V. M. Ramos et Ruy J. G. B. de Queiroz^[19]. Dans ce formalisme, Rocq prouve que les opérations sont correctes en ce sens qu’ils préservent le langage engendré par la grammaire.

Article d'exposition

• Martin Lange et Hans Leiß, « To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm », Informatica Didactica, vol. 8,‎ 2009 (lire en ligne) — Informatica Didactica est un journal électronique.

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, présentation en ligne)
• 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 C. Martin, Introduction to languages and the theory of computation, McGraw-Hill Science/Engineering/Math, 2003, 543 p. (ISBN 978-0-07-232200-2 et 0072322004)
• (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).
• (en) Michael Sipser, Introduction to the theory of computation, Boston, MA, Cengage Learning, 2013, 3^e éd., 480 p. (ISBN 978-1-133-18779-0, OCLC 761858892, lire en ligne).
• (de) Ingo Wegener, Theoretische Informatik : Eine algorithmenorientierte Einführung, Vieweg+Teubner Verlag, coll. « Leitfäden und Monographien der Informatik », 1993, 238 p. (ISBN 978-3-519-02123-0 et 3519021234)

Cours en ligne

• Antoine Rozenknop, « Modèles de Langages et Analyse Syntaxique », Université Paris Nord, 7 octobre 2010.
• Jacques Désarménien, « Chapitre 4 : Grammaires non contextuelles », Université de Marne-la-Vallée.
• Richard Cole, « 'Converting CFGs to CNF (Chomsky Normal Form) », New York University, 17 octobre 2007. — utilise l’ordre TERM, BIN, START, DEL, UNIT.

Outil pédagogique pour la conversion d'une grammaire en forme normale de Chomsky

• Grammaire non contextuelle
• Grammaire contextuelle
• Forme normale de Greibach
• Compilation
• Forme de Backus-Naur
• Algorithme de Cocke-Younger-Kasami
• Forme normale de Kuroda

• Portail de l'informatique théorique