Voir la source de Forme normale de Chomsky


En [[informatique théorique]], et notamment en [[théorie des langages]], une [[grammaire algébrique|grammaire non contextuelle]] est en <dfn>forme normale de Chomsky</dfn> si et seulement si toutes ses règles de production sont de la forme :
# <math>X\to YZ</math> ;
# ou <math>X\to a</math> ;
# ou <math>S\to\varepsilon</math>

où <math>X, Y, Z</math> sont des [[Symboles terminaux et non-terminaux|symboles non terminaux]], <math>a</math> est un [[Symboles terminaux et non-terminaux|symbole terminal]], <math>S</math> est l'axiome de la grammaire, et <math>\varepsilon</math> 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.

== Historique ==
La forme normale de Chomsky tient son nom du linguiste américain [[Noam Chomsky]], qui a conçu également [[Hiérarchie de Chomsky|la hiérarchie qui porte son nom]], et qui a décrit cette forme normale à cette occasion dans un article publié en [[1959]]<ref>{{article|langue=en|titre=On Certain Formal Properties of Grammars|volume=2|année=1959|doi=10.1016/s0019-9958(59)90362-6|pages=137–167|prénom=Noam|nom=Chomsky|journal=''[[Information and Computation|Information and Control]]''|url=http://www.sciencedirect.com/science/article/pii/S0019995859903626/pdf?md5=9d466f851651bd592afa5ee561b7a0b0&pid=1-s2.0-S0019995859903626-main.pdf|format=pdf}}.</ref>.

== Variantes de définition ==

Une variante de la définition consiste à ne pas permettre le mot vide : seules des règles de la forme 
: <math>X \to YZ</math> ou <math>X \to a</math>,
sont permises  où <math>X</math>, <math>Y</math> et <math>Z</math> sont des symboles non terminaux et <math>a</math> est un [[Symboles terminaux et non terminaux|symbole terminal]]. C'est la définition adoptée par  exemple par Carton<ref>{{harvsp|Carton|2008}}</ref>  ou Hopcroft ''et. al.'' <ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007}}</ref>. Bien entendu, ces grammaires n'engendrent pas le mot vide.

Une autre variante<ref name="LL5" />{{,}}<ref>{{Ouvrage |langue=fr |auteur1=Romain Legendre |auteur2=François Schwarzentruber |titre=Compilation : analyse lexicale et syntaxique |sous-titre=Du texte à sa structure en informatique |éditeur=Ellipse |lieu=Paris |année=2015 |pages totales=312 |isbn=978-2-340-00366-8}}</ref> 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 ».

== Propriétés et utilisations ==
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 <math>n>0</math> se fait donc toujours en <math>2n-1</math> étapes : il y a <math>n-1</math> étapes de type (1) et <math>n</math> é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 <math>2n-1</math> nœuds internes et <math>n</math> 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 [[Langage formel|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 [[algorithme]]s généraux d'analyse syntaxique, comme l'[[algorithme de Cocke-Younger-Kasami]], emploient cette forme normale.

== Conversion d'une grammaire en forme normale de Chomsky ==

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<ref>
{{harvsp|Hopcroft|Ullman|1979|p=87-94}}.</ref>{{,}}<ref>
{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|loc=Section 7.1 : ''Normal Forms for Context-Free Grammars'', {{p.|261-275}}}}.</ref>{{,}}<ref>
{{harvsp|Wegener|1993|loc=Section 6.2 ''Die Chomsky-Normalform für kontextfreie Grammatiken'', {{p.|149-152}}}}.</ref>{{,}}<ref>
{{harvsp|Carton|2008|loc=Section 2.1.4 : ''Forme normale quadratique'', {{p.|80-82}}}}.</ref>{{,}}
<ref>{{harvsp|Sipser|2013|loc=Section 2.1: ''Context-free grammars''. Chomsky normal form {{p.|108}}}}.</ref>{{,}}<ref>
{{harvsp|Martin|2003|loc=Section 6.6 : ''Simplified forms and normal forms'', {{p.|237-240}}}}.</ref>
{{,}}<ref>
{{harvsp|Linz|2001|loc=Chapter 6 : ''Simplification of context-free grammars'', {{p.|149-164}}}}</ref>. Dans un article pédagogique, Lange et Leiß<ref name="XX">{{harvsp|Lange|Leiß|2009|id=LL}}.</ref> 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 
{{harvsp|Carton|2008|loc=(Section 2.1.2 : ''Grammaires réduites'', {{p.|79}})}} ou « eliminating useless symbols » chez {{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|loc=(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<ref name="XX" /> comme la place que prend l'écriture des règles, sont
:<math>|G|=\sum_{X\to \alpha} |X\alpha|</math>
où la sommation porte sur toutes les règles <math>X\to \alpha</math> de la grammaire. En particulier, une ε-règle contribue pour 1 dans la somme.
===START : Suppression de l’axiome dans les membres droits de règles ===
Pour cela, on introduit un nouveau symbole <math>S_0</math> qui devient l'axiome, et la règle 
:<math>S_0\to S</math>, 
où <math>S</math> est l’ancien axiome. Ceci ne modifie pas le langage engendré, et la variable <math>S_0</math> ne figure pas dans un membre droit de règle.

===TERM : Suppression des lettres terminales dans les membres droits de règles de longueur au moins 2 ===
Si une lettre terminale <math>a</math> figure dans un membre droit de règle de longueur au moins 2, on la remplace par une nouvelle <math>N_a</math> et on ajoute la nouvelle règle  
:<math>N_a\to a</math>
et on remplace la règle ci-dessus par
: <math>X \to WN_aT</math>
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''|.

===BIN : Suppression des membres droits avec plus de deux symboles ===
On remplace une règle
: <math>X \to Y_1 Y_2\cdots Y_n</math>, 
par les règles 
: <math>X \to Y_1 Z_1,\ Z_1 \to Y_2 Z_2, \ldots,\ Z_{n-2} \to Y_{n-1} Y_n</math>,
où les <math>Z_i</math> sont des nouveaux symboles non terminaux<ref>
{{harvsp|Hopcroft|Ullman|1979|p=93}}.</ref>{{,}}<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|p=272}}</ref>. Cette opération au plus triple la taille de la grammaire.

===DEL : Élimination des ε-règles ===
Une ε-règle est une règle de la forme  
: <math>X \to \varepsilon</math>, 
où  <math>X</math> 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 
: <math>X \to Y_1\cdots Y_n</math> telle que <math>Y_1, \ldots, Y_n</math> sont tous annulables.
Pour toute variable <math>X</math>, annulable ou non, toute règle 
: <math>X \to Y_1\cdots Y_n</math>
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)<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|p=265}}.</ref>.

Par exemple, dans la grammaire suivante avec axiome ''S''<sub>0</sub>,
: ''S''<sub>0</sub> → ''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''<sub>0</sub> ne le sont. Dans la version intermédiaire suivante, on a coloré les variables à supprimer :
: ''S''<sub>0</sub> → ''AbB'' | ''{{Coloré|green|A}}bB'' | ''Ab{{Coloré|green|B}}''  | ''{{Coloré|green|A}}b{{Coloré|green|B}}'' | ''C''
: ''B'' → ''AA'' | ''{{Coloré|green|A}}A''| ''A{{Coloré|green|A}}'' | ''{{Coloré|green|A}}ε{{Coloré|green|A}}'' | ''AC'' | ''{{Coloré|green|A}}C ''
: ''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''<sub>0</sub> → ''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.

=== UNIT : Suppression des règles unité ===

Une ''règle unité'' est une règle de la forme 
: <math>X\to Y</math> 
où  <math>X</math> et <math>Y</math> sont des variables, et plus généralement une règle
: <math>X\to WYT</math>,
où toutes les variable de <math>WT</math> sont annulables. Pour éliminer ce type de règles, on la remplace
par la règle 
: <math>X\to \alpha</math>
pour chaque règle
: <math>Y \to \alpha</math>
sauf si c'est une règle unité précédemment enlevée<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|p=268}}.</ref>. Cette technique est complétée dans le cas de cycles (comme l'existence de trois règles <math>X \to Y, Y \to Z, Z \to X</math>) 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''|<sup>2</sup>.

=== Ordre des transformations ===

{| class="wikitable" style="float:right"
|-
! colspan=6 | Préservation<br> des propriétés des transformations
|-
| colspan=6 | {{Y&}} la transformation  ''X'' préserve le résultat de ''Y''<br>{{N&}}  la transformation  ''X'' peut altérer le résultat de ''Y''.
|-
| <sub>''X''</sub>'''\'''<sup>''Y''</sup>
|           '''START''' ||'''TERM'''||'''BIN'''||'''DEL'''||'''UNIT'''
|-
| '''START''' ||        || {{Y&}}   || {{Y&}}  || {{Y&}}  || {{N&}} 
|-
| '''TERM'''  || {{Y&}} ||          || {{N&}}  || {{Y&}}  || {{Y&}} 
|-
| '''BIN'''   || {{Y&}} || {{Y&}}   ||         || {{Y&}}  || {{Y&}} 
|-
| '''DEL'''   || {{Y&}} || {{Y&}}   || {{Y&}}  ||         || {{N&}} 
|-
| '''UNIT'''  || {{Y&}} || {{Y&}}   || {{Y&}}  ||({{Y&}})<sup>*</sup>||  
|-
| colspan=6 | <sup>*</sup>'''UNIT''' conserve le résultat de '''DEL'''<BR>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''|<sup>2</sup> à 2<sup>2|''G''|</sup> pour une grammaire de taille |''G''|<ref>{{harvsp|Lange|Leiß|2009|id=LL|p=7}}.</ref>. 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<sup>2''n''</sup> règles, et sinon est linéaire. '''UNIT''' peut provoquer une augmentation quadratique de la taille<ref name="LL5">{{harvsp|Lange|Leiß|2009|id=LL|p=5}}.</ref>. 

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

=== Preuve de correction ===
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 (logiciel)|Rocq]] a été entreprise par Marcus V. M. Ramos
et Ruy J. G. B. de Queiroz<ref>{{article|auteur1=Marcus V. M. Ramos
| auteur2=Ruy J. G. B. de Queiroz
| titre=Formalization of simplification for context-free grammars
| périodique= préprint arXiv 
| arxiv=1509.02032v2
| mois=octobre
| année=2015|id=RamosQueiroz2015}}.</ref>. Dans ce formalisme, Rocq prouve que les opérations sont correctes en ce sens qu’ils préservent le langage engendré par la grammaire.

== Références ==
{{références
 | taille = 30
}}

== Bibliographie ==
; Article d'exposition
*{{article |url=http://ddi.cs.uni-potsdam.de/InformaticaDidactica/LangeLeiss2009.pdf|auteur1= Martin Lange |auteur2 =Hans Leiß|titre=To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm|journal=[http://www.informatica-didactica.de/cmsmadesimple/index.php?page=home Informatica Didactica] |volume=8|date=2009|id=LL}} — [http://www.informatica-didactica.de/cmsmadesimple/index.php?page=home ''Informatica Didactica'']  est un journal électronique.
; Manuels
<!-- Carton -->
* {{Ouvrage| langue=fr| auteur1=Olivier Carton| titre=Langages formels, calculabilité et complexité| sous-titre=licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques| éditeur=Vuibert| lieu=Paris| année=2008| pages totales=237| isbn=978-2-7117-2077-4| présentation en ligne=http://liafa.jussieu.fr/~carton/Lfcc/| id=Carton2008}} 
<!-- Hopcroft -->
* {{Ouvrage
 | auteur1=[[John Hopcroft|John E. Hopcroft]]
 | auteur2=[[Jeffrey Ullman|Jeffrey D. Ullman]]
 | titre=Introduction to Automata Theory, Languages and Computation
 | éditeur=Addison-Wesley
 | année=1979
 | isbn=
}}
* {{Introduction to Automata Theory, Languages, and Computation}}
<!-- Martin -->
* {{Ouvrage | langue=en | auteur1=John C. Martin | titre=Introduction to languages and the theory of computation | éditeur=McGraw-Hill Science/Engineering/Math | année=2003 | pages totales=543 | isbn=978-0-07-232200-2 | isbn2=0072322004}}
<!-- Linz -->
*{{Ouvrage | langue=en | auteur1=Peter Linz | titre=An Introduction to Formal Languages and Automata | éditeur=Jones & Bartlett Learning | année=2001 | pages totales=410 | isbn=978-0-7637-1422-2 | isbn2=0763714224 | lire en ligne=https://books.google.com/books?id=Cgooanwdo9AC&printsec=frontcover}}.
<!-- Sipser -->
* {{Ouvrage | langue=en | auteur1=Michael Sipser | titre=Introduction to the theory of computation | éditeur=Cengage Learning | lieu=Boston, MA | année=2013 | numéro d'édition=3 | pages totales=480 | isbn=978-1-133-18779-0 | oclc=761858892 | lire en ligne=https://books.google.com/books?id=P3f6CAAAQBAJ&printsec=frontcover}}.
<!-- Wegener -->
*{{Ouvrage | langue=de | auteur1=[[Ingo Wegener]] | titre=Theoretische Informatik | sous-titre=Eine algorithmenorientierte Einführung | éditeur=Vieweg+Teubner Verlag | collection=Leitfäden und Monographien der Informatik | année=1993 | pages totales=238 | isbn=978-3-519-02123-0 | isbn2=3519021234}}

; Cours en ligne
* {{Lien web|url= http://lipn.univ-paris13.fr/~rozenknop/Cours/ITCN_MLAS/Seance2/Cours.beamer.pdf
|titre= Modèles de Langages et Analyse Syntaxique|auteur = Antoine Rozenknop |date = 7 octobre 2010 |éditeur=Université Paris Nord}}.
* {{Lien web|url= http://www-igm.univ-mlv.fr/~desar/Cours/automates/ch4.pdf|titre= Chapitre 4 : Grammaires non contextuelles|auteur=Jacques Désarménien|éditeur= Université de Marne-la-Vallée}}.
* {{Lien web|url= http://cs.nyu.edu/courses/fall07/V22.0453-001/cnf.pdf|titre= 'Converting CFGs to CNF (Chomsky Normal Form)|auteur=Richard Cole|jour= 17|mois= octobre |année= 2007|éditeur= New York University}}. — utilise l’ordre  TERM, BIN, START, DEL, UNIT.

== Lien externe ==
[http://compilation.irisa.fr/cnf/ Outil pédagogique pour la conversion d'une grammaire en forme normale de Chomsky]

== Voir aussi ==
*[[Grammaire non contextuelle]]
*[[Grammaire contextuelle]]
*[[Forme normale de Greibach]]
*[[Compilation (informatique)|Compilation]]
*[[Forme de Backus-Naur]]
*[[Algorithme de Cocke-Younger-Kasami]]
*[[Forme normale de Kuroda]]

{{portail|Informatique théorique}}

[[Catégorie:Langage formel]]
[[Catégorie:Noam Chomsky]]