Hiérarchie de Chomsky

Hiérarchie de Chomsky

En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky- Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels engendrées par les grammaires), décrite par Noam Chomsky en 1956 [1].

Présentation

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(n3), les langages contextuels (type 1) en DTIME(nM), 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.

Other Languages