Hiérarchie de Chomsky

La hiérarchie introduite par Noam Chomsky repose sur le modèle de grammaire formelle. Il définit les classes de sa hiérarchie comme modèles possibles pour la description des propriétés structurelles des langues naturelles. Noam Chomsky a proposé une classification en quatre types de langages, des type 0 au type 3. Cette terminologie initiale s’est maintenue, mais d’autres noms sont maintenant plus fréquents. Chomsky a présenté ces familles en termes de grammaires formelles, et les diverses classes de grammaires sont définies par des restrictions successives dans la forme des règles.

Une propriété remarquable de la classification de Chomsky est que, pour chaque type, il existe une famille d’automates qui acceptent exactement les langages de ce type. Ces automates varient par la nature et l’emploi de la mémoire auxiliaire. La traduction en classes de complexité est moins nette : les langages rationnels (type 3) sont dans DTIME(n), les langages algébriques (type 2) dans DTIME(n³), les langages contextuels (type 1) en DTIME(n^M), où M dépend de la grammaire, mais la réciproque n'est pas vraie.

La classification de Chomsky, reprise dans la presque totalité des manuels d’enseignements de l'informatique, s'est révélée très fructueuse dans ses applications, notamment dans la conception et l’analyse des langages de programmation et la compilation de ces langages. Les langages rationnels et algébriques ont fait l’objet d'études théoriques très poussées par le passé. Les langages contextuels sont surtout employés dans la description de langues naturelles.

Chomsky a défini quatre classes de grammaires, nommées de type 0 à type 3, et donc aussi quatre classes de langages, engendrés par ces grammaires hiérarchiquement imbriquées :

1. Les langages de type 0 sont les plus généraux : ce sont les langages récursivement énumérables.
2. Les langages de type 1 sont les langages contextuels, en anglais « context-sensitive ».
3. Les langages de type 2 sont appelés langages algébriques ou « hors contexte », en anglais « context-free ».
4. Les langages de type 3 sont les langages « réguliers » ou langages rationnels.

Tous les langages de type 3 sont des langages de type 2. Tous les langages de type 2 sont des langages de type 1. Tous les langages de type 1 sont des langages de type 0. La table suivante résume la correspondance entre types de grammaire, langages et machines.

Grammaire	Règles de production	Langage	Machine
type 0	${\displaystyle \alpha \rightarrow \beta }$	récursivement énumérable	Machine de Turing
type 1	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$	contextuel	Automate linéairement borné
type 2	${\displaystyle A\rightarrow \gamma }$	algébrique	Automate à pile non déterministe
type 3	${\displaystyle A\rightarrow aB,\quad A\rightarrow a}$	rationnel	Automate fini

Dans la présentation formelle ci-dessous, ${\displaystyle V}$ est le vocabulaire de la grammaire, composé des symboles terminaux et non-terminaux, ${\displaystyle N}$ est l'ensemble des symboles non-terminaux, et ${\displaystyle \varepsilon }$ est le mot vide.

• Langages réguliers :
  ${\displaystyle a^{*}b^{*},\quad (aaab)^{*},\quad \{a^{3i}:i>0\}}$.
• Langages algébriques qui ne sont pas rationnels :
  ${\displaystyle \{a^{i}b^{i}:i>0\}\,}$, l'ensemble des palindromes (qui est même un langage linéaire, comme le précédent), le langage de Dyck
• Langages contextuels qui ne sont pas algébriques :
  ${\displaystyle \{a^{i}b^{i}c^{i}:i>0\},\quad \{a^{i}b^{k}c^{i}d^{k}:i>0,k>0\},\quad \{uu:u\in \{a,b\}^{*}\}}$.

Voir aussi les exemples sur la page grammaire formelle. La théorie des langages formels dispose de nombreux outils pour affirmer, ou infirmer, le type d'un langage (rationnel, algébrique etc.). La construction explicite d'une grammaire reconnaissant un langage donné n'est pas toujours facile.

La hiérarchie originale de Chomsky comprenait quatre classes. D'autres classes sont souvent intercalées[3] - [4] - [5] :

• entre le type 0 et le type 1, les langages récursifs, qui sont acceptés par les machines de Turing qui s'arrêtent toujours ;
• entre le type 1 et le type 2, les langages à grammaires indexées, définis par des grammaires plus générales que les grammaires contextuelles ;
• entre le type 2 et le type 3, les langages algébriques déterministes, pour lesquels il existe une caractérisation par automate, mais pas par les grammaires[6] ;
• aussi entre le type 2 et le type 3, les langages linéaires, engendrés par les grammaires linéaires.

Les grammaires d'arbres adjoints[7] - [8] définissent une famille entre les langages algébriques et les langages contextuels. Ils sont acceptés par les automates à piles embarquéee[9]. Ces grammaires font partie des grammaires qui permettent de mieux cerner la structure des langues naturelles, regroupés sous le nom langage légèrement sensible au contexte (en)[10].

D'autres raffinements existent, qui montrent que la structure n'est pas « linéaire » : par exemple, si l'on compare les langages linéaires et les langages algébriques déterministes, on s’aperçoit que ces familles ne sont pas contenues l'une dans l'autre.

La hiérarchie de Chomsky concerne uniquement le domaine du calculable défini paradigmatiquement par ce que peut calculer une machine de Turing. Au-delà existent d'autres hiérarchies de langages dont la hiérarchie arithmétique.

• (en) Noam Chomsky, « On certain formal properties of grammars », Information and Control, vol. 2, n^o 2,‎ juin 1959, p. 137-167 (DOI 10.1016/S0019-9958(59)90362-6, lire en ligne )
• (en) Noam Chomsky, « A note on phrase structure grammars », Information and Control, vol. 2, n^o 4,‎ décembre 1959, p. 393-395 (DOI 10.1016/S0019-9958(59)80017-6)
• (en) Noam Chomsky, « Context-free grammars and pushdown storage », RLE Quart.Prog. Rept., MIT Research Laboratories of Electronics, n^o 65,‎ 1962, p. 393-395
• (en) John Hopcroft et Jeffrey 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) — Ne contient plus de chapitre spécifique à la hiérarchie de Chomsky
• (en) Daniel I. A. Cohen, Introduction to Computer Theory, John Wiley & Sons, 1997
• (en) Peter Linz, An introduction to Formal Languages and Automata, Jones and Bartlett, 2001, 3^e éd., 410 p. (ISBN 978-0-7637-1422-2, lire en ligne)

• Théorie des automates
• Théorie des langages
• Langage formel
• Grammaire formelle
• Marcel-Paul Schützenberger