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.

Définition

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

• T : symboles terminaux (appelé également "alphabet" ou "vocabulaire terminal")
• N : symboles non-terminaux
• R : règles
• S (S ∈ N) : axiome (symbole de départ)

Les règles définissent les lois d'enchassement 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 moins précise que celle des langages de programmation.

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.

Grammaires générales (type 0)

Les règles sont de la forme : w1 ↦ w2 où w1 et w2 ∈ (N ∪ T)*

Cette catégorie est impossible à traiter, la grammaire est très puissante, mais le temps pour savoir si une phrase appartient ou non à celle-ci n'est pas forcément fini.

Grammaires contextuelles (type 1)

Les règles sont de la forme : sXt ↦ swt où s, w et t ∈ (N ∪ T)* et X ∈ N

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.

Grammaires hors-contexte (type 2)

Les règles sont de la forme : X ↦ w où X ∈ N et w ∈ (N ∪ T)*

Ici, plus de contexte, ce qui signifie que les éléments non-terminaux sont traités individuellement.

Grammaires régulières (type 3)

Les règles sont de la forme : X ↦ a ou X ↦ Ya (ou aY) où X et Y ∈ N et a ∈ T

Grammaires à choix finis (type 4)

Les règles sont de la forme : X ↦ a où X ∈ N et a ∈ T

exemple

une chaîne commence par un a et se termine par un z; elle peut contenir 0 à n = séparé par 1 à n - entre elles.

Mots (valides) :

• az
• a=z
• a=-=z
• a-=-=-z
• a

  ---

  -z

Réponse :

T = {a,z,=,-} N = {S,A,B} S = {S} R = { S ↦ Az, A ↦ A-, A ↦ B=, B ↦ A-, A ↦ a, B ↦ a }

Langage formel | Syntaxe

Chomsky-hiërargie | Йерархия на Чомски | Chomského hierarchie | Chomsky-Hierarchie | Chomsky–Schützenberger hierarchy | Jerarquía de Chomsky | Chomskyn hierarkia | Gerarchia di Chomsky | チョムスキー階層 | 촘스키 위계 | Hierarchia Chomsky'ego | Hierarquia de Chomsky | Ierarhia Chomsky | Chomského hierarchia | 乔姆斯基谱系