Hiérarchie de Chomsky

En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky est une classification des langages formels et des grammaires formelles, décrite par Noam Chomsky en 1956^[1].

Cette section ne cite pas suffisamment ses sources. Merci d'ajouter en note des références vérifiables ou le modèle {{Référence souhaitée}}.

La hiérarchie de Chomsky constitue la seule classification des grammaires génératives calculables; à chaque type de grammaire correspond un type d'automate. Il est formellement impossible de concevoir d'autres classes de grammaires comme des classes d'automates. De même que thèse de Church-Turing affirme qu'il ne peut exister de langage calculable supérieur à ceux générés par une Machine de Turing, la hiérarchie des classes de grammaire mène à la thèse qu'il n'existe pas de langage calculable qui n'entre pas strictement dans une de ces classes^{[réf. souhaitée]}. En revanche, il est possible de caractériser rigoureusement des hiérarchies plus vastes d'ensembles contenant des éléments non calculables, comme notamment la hiérarchie arithmétique^{[2],[3],[4],[5],[6]}.

Les classes (ensembles) de langages L0, L1, L2, L3 (chaque langage étant un ensemble de mots) de la hiérarchie sont strictement imbriquées : $L3 \subset L2 \subset L1 \subset L0 \subset U$, U est l'univers de tous les langages de mots finis et infinis possibles. Le rapport ||L0|| / ||U|| tend vers zéro, il s'agit de la densité d'incomplétude, soit le rapport de la cardinalité du dénombrable sur celui de l'indénombrable.

La hiérarchie originale de Chomsky comprenait quatre classes, il est facile d'en ajouter deux : la grammaire à choix finis qui génère un sous ensemble si pauvre des grammaires régulières qu'elle est généralement omise et les langages hors contexte déterministes se positionnant entre les langages réguliers et les langages hors contexte^[7]. Il est également possible de séparer les langages récursivement énumérables en deux catégories : les langages acceptés par les machines de Turing en un temps fini (langages récursifs) et ceux acceptés en un temps infini (récursivement énumérables).

En 1975 fut découverte la grammaire d'arbres adjoints (légèrement sensible au contexte) par A.K. Joshi et ses collègues^{[8], [9]} venant se placer entre les langages hors-contextes et les langages sensibles au contexte. C'est seulement en 1988 que fut décrit l'automate acceptant cette grammaire par K. Vijay-Shanker dans sa thèse de doctorat^[10] ; les automates à pile embarquée. Cette découverte permis de clarifier la frontière de la machine de Turing et de créer de nouvelles grammaires : linéaires, indexées, etc. Ainsi que de créer trois nouvelles classes de langages : indexé, légèrement sensible au contexte et arbre adjoints. Les langages sensibles au contexte semblent se diviser encore (grammaire sensible au contexte croissante)^[11],[12].

Définition

Une grammaire formelle est constituée de quatre objets :

• T : ensemble des symboles terminaux, appelé également « alphabet terminal » ou « vocabulaire terminal », noté aussi Σ ;
• N : ensemble des symboles non terminaux ou alphabet de variables;
• R : ensemble des règles ;
• S (S ∈ N) : axiome (symbole de départ).

L'alphabet terminal est aussi noté Σ ou A. Ces alphabets sont finis, ainsi que l'ensemble de règles. Dans la suite, on note V = N ∪ T et on suppose que N et T sont disjoints.

Une règle est un couple (x,y) de mots sur V, avec la condition que x contient au moins une variable. On écrit souvent $x\to y$ au lieu de (x,y).

Une dérivation immédiate du mot u en le mot v consiste à remplacer, dans u, une occurrence de x par y; en d'autres termes, u dérive immédiatement en v par l'emploi de la règle (x,y) si u=pxs et v=pys pour des mots p et s. Une dérivation est une suite de dérivations immédiates consécutives. En d'autres termes, la dérivation est la fermeture réflexive et transitive de la relation de dérivation immédiate.

Le langage engendré par une grammaire est l'ensemble des mots sur l'alphabet terminal, donc ne contenant plus de variables, qui l'on peut dériver à partir de l'axiome S.

Les règles d'une grammaire définissent les lois d’enchâssement des mots du langage. Les langues naturelles ont une grammaire bien plus complexe que celle des langages de programmation ; il n’est pas possible de la formaliser entièrement de cette façon.

Quatre classes de grammaires et de langages

Chomsky a défini quatre classes de grammaires, et donc de langages engendrés par ces grammaires (type 0 à type 3) hiérarchiquement imbriquées. Les langages de type 0 sont les plus généraux: ce sont les langages récursivement énumérables. Ils contiennent les langages de type 1, les langages « contextuels » ou « contexte-sensitifs ». Les langages de type 2 sont appelés « hors-contexte » ou langage algébriques). Ils contiennent eux-mêmes les langages de type 3, les langages « réguliers » ou langages rationnels. Parfois, on ajoute une dernière classe, composée des langages finis.

Type 0: grammaires générales

Aucune condition n'est imposée aux règles. Elles ont la forme :

$\alpha \rightarrow \beta\quad\quad(\alpha \in V^*NV^*, \beta \in V^*)$

Ces grammaires génèrent la classe des langages récursivement énumérables. Ce sont exactement les langages reconnaissables par machine de Turing. Le problème de l'appartenance d'un mot à un langage de cette classe est alors indécidable.

Type 1: grammaires contextuelles

Article détaillé: Grammaire contextuelle

Les règles sont de la forme :

$\alpha A\beta \rightarrow \alpha\gamma\beta\qquad(A \in N, \alpha,\beta,\gamma \in V^*,\gamma \neq \varepsilon)$

Autrement dit, toute règle comprend un non-terminal entouré de deux mots qui décrivent le contexte dans lequel la variable peut être remplacée. Ces grammaires sont dites contextuelles (en anglais context-sensitive), car le remplacement d'un élément non-terminal peut dépendre des éléments autour de lui : son contexte. Les langages produits, appelés langages contextuels ou sensibles au contexte, sont exactement ceux reconnus par une machine de Turing linéairement bornée non déterministe. Des formulations équivalentes existent pour les grammaires définissant les langages contextuels.

Type 2: grammaires non contextuelles

Article détaillé : Grammaire non contextuelle.

Les règles sont de la forme :

$A \rightarrow \gamma\qquad(A \in N, \gamma \in V^*)$

Ce sont des grammaires contextuelles où le contexte est vide, ce qui signifie que les symboles non-terminaux sont traités indépendamment de la place où ils apparaissent. Ces grammaires engendrent exactement les langages algébriques, appelés aussi langages hors-contexte, langages acontextuels, ou langages non contextuels. Ils sont reconnus par un automate à pile.

Type 3: grammaires régulières

Les grammaires régulières sont soit les grammaires linéaires gauches ou les grammaires linéaires droites:

• Dans les grammaires linéaires gauches, les règles sont de la forme :

$A \rightarrow Ba,\quad A \rightarrow a\qquad(A,B \in N, a \in T)$

• Dans les grammaires linéaires droites, les règles sont de la forme :

$A \rightarrow aB,\quad A \rightarrow a\qquad(A,B \in N, a \in T)$

Les grammaires régulières engendrent les langages rationnels. En effet, une grammaire régulière se transforme facilement en un automate fini (théorème de Kleene).

On ne peut pas autoriser les deux types de règles simultanément dans une grammaire sans sortir la classe des langages rationnels: on obtient les grammaires linéaires qui constituent une classe intermédiaire entre le type 2 et le type 3. Les règles d'une grammaire linéaire sont de la forme :

$A \rightarrow aBb,\quad A \rightarrow a\qquad(A,B \in N, a,b \in T\cup\varepsilon)$

Exemples

• Langages réguliers : $a^*b^*,\quad (aaab)^*,\quad \{a^{3i} : i>0\}$.
• Langages algébriques qui ne sont pas rationnels :

$\{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 :

$\{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.

Notes et références

1. ↑ Noam Chomsky, « Three models for the description of language », dans IRE Transactions on Information Theory, n^o 2, 1956, p. 113–124 [texte intégral] 
2. ↑ COHEN D.I.A.: Introduction to Computer Theory. John Wiley & Sons, 1997
3. ↑ HARRISON M.A.: Introduction to Formal Language Theory. Addison-Wesley, 1978
4. ↑ HOPCROFT J.E., ULLMAN J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979
5. ↑ RAYWARD-SMITH V.J.: A First Course in Computability. McGraw-Hill Book Company, London 1986
6. ↑ MARTIN J.C.: Introduction to Languages and the Theory of Computation. Second Edition, McGraw-Hill Int., 1997
7. ↑ Cohen, Daniel.I.A.: Introduction to Computer Theory, Chap. 30 : The Chomsky Hierarchy, John Wiley & Sons, 1997
8. ↑ A.K. Joshi, L.S. Levy, and M. Takahashi, « Tree adjunct grammars », Journal of Computer Systems Science, 10(1), 1975.
9. ↑ Unification-Based Tree Adjoining Grammars
10. ↑ K. Vijay-Shanker, « A Study of Tree-Adjoining Grammars », dans Ph.D. Thesis, University of Pennsylvania, janvier 1988 
11. ↑ Robert McNaughton, «An insertion into the Chomsky hierarchy?», 1999
12. ↑ T. Jurdziński, K. Lorys, G. Niemann, F. Otto, «Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages», Journal of Automata, Languages and Combinatorics, Volume 9 Issue 4, October 2004

Articles connexes

• Théorie des automates
• Grammaire formelle
• Automate fini
• Langage rationnel
• Noam Chomsky
• Marcel-Paul Schützenberger