Hiérarchie de Chomsky 24082016

Hiérarchie de Chomsky

Hiérarchie de Chomsky, avec classes de langages et classes d'automates associés.

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

Les classes de langages L0, L1, L2, L3 (chaque langage étant un ensemble de mots) de la hiérarchie sont strictement imbriquées : ${\displaystyle L3\subsetneq L2\subsetneq L1\subsetneq L0\subsetneq U}$. Ici ${\displaystyle U}$ est l'univers de tous les langages.

Sommaire

  [afficher] 

Définition[modifier | modifier le code]

Une grammaire formelle est constituée de quatre objets :

• ${\displaystyle T}$ : ensemble fini de symboles terminaux, appelé alphabet terminal ;
• ${\displaystyle N}$ : ensemble fini de symboles non terminaux ou alphabet des variables ;
• ${\displaystyle R}$ : ensemble fini de règles ;
• ${\displaystyle S(S\in N)}$ : axiome (symbole de départ).

Les alphabets ${\displaystyle T}$ et ${\displaystyle N}$ sont disjoints. L'alphabet terminal est parfois noté ${\displaystyle \Sigma }$ ou ${\displaystyle A}$. Dans la suite, on note ${\displaystyle V=T\cup N}$. ${\displaystyle V^{*}}$ est l'ensemble des mots sur ${\displaystyle V}$. ${\displaystyle \varepsilon }$ est le mot vide et ${\displaystyle V^{+}=V^{*}\backslash \{\varepsilon \}}$.

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

Une dérivation immédiate du mot ${\displaystyle u}$ en le mot ${\displaystyle v}$ consiste à remplacer, dans ${\displaystyle u}$, une occurrence de ${\displaystyle x}$ par ${\displaystyle y}$ ; en d'autres termes, ${\displaystyle u}$dérive immédiatement en ${\displaystyle v}$ par l'emploi de la règle ${\displaystyle (x,y)}$ si ${\displaystyle u=pxs}$ et ${\displaystyle v=pys}$ pour des mots ${\displaystyle p}$ et ${\displaystyle 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, que l'on peut dériver à partir de l'axiome ${\displaystyle 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[modifier | modifier le code]

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. 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, en anglais « context-sensitive ». Les langages de type 2 sont appelés langage algébriques ou « hors contexte », en anglais « context-free ». 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[modifier | modifier le code]

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

${\displaystyle \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 indécidable.

Type 1 : grammaires contextuelles[modifier | modifier le code]

Article détaillé : Grammaire contextuelle.

Les règles sont de la forme :

${\displaystyle \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 non déterministe à mémoire linéairement bornée, appelés couramment automates linéairement bornés. D'autres formulations équivalentes existent pour les grammaires définissant les langages contextuels.

Type 2 : grammaires non contextuelles ou algébriques[modifier | modifier le code]

Article détaillé : Grammaire non contextuelle.

Les règles sont de la forme :

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

Un telle règle peut être vue comme une règle contextuelle où le contexte des règles est vide, à condition que le membre droit ${\displaystyle \gamma }$ n'est pas le mot vide. L'adjectif « non contextuel » exprime le fait que les symboles non terminaux sont traités indépendamment de la place où ils apparaissent. Ces grammaires engendrent exactement leslangages 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[modifier | modifier le code]

Article détaillé : Grammaire régulière.

Les grammaires régulières sont soit les grammaires linéaires à gauche soit les grammaires linéaires à droite :

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

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

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

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

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

Inclusion des familles[modifier | modifier le code]

Les inclusions strictes des langages rationnels dans les langages algébriques :

${\displaystyle L3\subsetneq L2}$

et des langages contextuels dans les langages récursivement énumérables :

${\displaystyle \subsetneq L1\subsetneq L0}$

sont manifestes. L'inclusion des langages algébriques dans les langages contextuels :

${\displaystyle L2\subsetneq L1}$

doit être nuancée car un langage contextuel ne contient jamais le mot vide ε, donc l'énoncé exact est :

Un langage algébrique ne contenant pas le mot vide est un langage contextuel

ou, de manière équivalente :

Un langage algébrique est un langage contextuel éventuellement augmenté du mot vide.