Hiérarchie de Chomsky

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant la linguistique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

La hiérarchie de Chomsky est une classification des langages décrits par les grammaires formelles, proposée en 1956 par le linguiste Noam Chomsky. Elle est aujourd'hui largement utilisée en informatique, en particulier pour la conception d'interpréteurs ou de compilateurs, ou encore pour l'analyse des langages naturels.

Voir l'article Grammaire formelle pour une brève présentation de la hiérarchie de Chomsky.

[modifier] Définition

La grammaire d'un langage est définie grâce à quatre éléments :

T : symboles terminaux (appelé également "alphabet" ou "vocabulaire terminal", et noté aussi Σ)
N : symboles non terminaux
R : règles
S (S ∈ N) : axiome (symbole de départ)

Dans la suite on note V = N ∪ T, et on suppose que N et T sont disjoints. Les règles définissent les lois d'enchâssement des "mots" du langage, sa grammaire. En français par exemple, la structure : sujet + verbe + compléments est un élément de grammaire. Bien entendu, les langages naturels ont une grammaire bien plus complexe que celle des langages de programmation, et il n'est pas possible de la formaliser parfaitement.

[modifier] Cinq classes de grammaires

Selon Chomsky, les langages sont constitués en 5 classes (type 0 à type 4) hiérarchiquement imbriquées. Les langages de type 0 sont les plus généraux et incluent donc les langages de type 1 (dits "contextuels") qui incluent eux-mêmes les langages de type 2 (dits "hors-contexte") qui incluent eux-mêmes les langages de type 3 (dits "réguliers").

La classification des langages dépend des grammaires qui les engendrent. Ainsi, un langage de type i est engendré par une grammaire de type i. La classification des grammaires est faite en fonction de la forme de leurs règles.

[modifier] Générales (type 0)

Les règles sont de la forme :

$\alpha \rightarrow \beta$
$\alpha, \beta \in V^*, \alpha \neq \epsilon$

Ces grammaires sont très puissantes, mais le temps pour savoir si une phrase appartient ou non à celle-ci n'est pas forcément fini. Précisément, ce sont les langages récursivement énumérables, reconnaissables par machine de Turing : si une phrase appartient à une telle grammaire, on le saura en temps fini; sinon, la machine boucle sans donner de réponse.

[modifier] Contextuelles (type 1)

Les règles sont de la forme :

$\alpha A \beta \rightarrow \alpha \gamma \beta$
$A \in N, \alpha, \beta, \gamma \in V^*, \gamma \neq \epsilon$

Ces grammaires sont dites contextuelles, 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 sont exactement ceux reconnus par machine de Turing linéairement bornée non déterministes.

[modifier] Hors-contexte (type 2)

Article détaillé : Grammaire non contextuelle.

Les règles sont de la forme :

$A \rightarrow \gamma$
$A \in N, \gamma \in V^*$

Ici, plus de contexte, ce qui signifie que les éléments non-terminaux sont traités individuellement. Ces grammaires produisent exactement les langages hors-contexte, reconnaissables par automate à pile. En France on parle aussi de langages algébriques.

[modifier] Rationnelles (type 3)

Il faut distinguer deux cas (qui sont équivalents).

Les grammaires linéaires gauches. Les règles sont de la forme :

$A \rightarrow Ba$
$A \rightarrow a$
$A,B \in N, a \in \Sigma$

Les grammaires linéaires droites. Les règles sont de la forme :

$A \rightarrow aB$
$A \rightarrow a$
$A,B \in N, a \in \Sigma$

L'ensemble formé par les grammaires linéaires gauche et droite est l'ensemble des grammaires régulières.

Les langages rationnels sont exactement ceux reconnus par automate fini (théorème de Kleene).

Les grammaires linéaires sont des grammaires hors-contextes dont la partie droite de chaque règle contient au plus un symbole non-terminal ; elles 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$
$A \rightarrow a$
$A,B \in N, a,b \in \Sigma$

[modifier] À choix finis (type 4)

Les règles sont de la forme :

$A \rightarrow a$
$A \in N, a \in T$
Cette classe, très restreinte, est souvent omise dans la hiérarchie.

[modifier] Exemples

Les langages suivants sont rationnels : $a^*b^*,\ (aaab)^*,\ \{a^{3i} : i>0\}$ .
Quelques exemples typiques de langages hors-contexte 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), l'ensemble des expressions bien parenthésées, comme ( [ ] ( ) ) mais pas ( [ ) ], les expressions arithmétiques parenthésées, $\{a^i b^i c^k d^k : i>0, k>0\}\,$ .