Hiérarchie de Chomsky

vignette|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 respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (32)

Cours associés (4)

Séances de cours associées (19)

MATH-458: Programming concepts in scientific computing

The aim of this course is to provide the background in scientific computing. The class includes a brief introduction to basic programming in c++, it then focus on object oriented programming and c++ s

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

Couvre les hiérarchies de classe, l'appariement des motifs, les valeurs de fonction et les appels de fonction dans Scala.

Explore les grammaires formelles, les algorithmes d'analyse, l'efficacité de l'algorithme CYK et la correction syntaxique dans le traitement du langage naturel.

Couvre les grammaires sans contexte, les règles de production, les automates, l'analyse syntaxique et les techniques d'analyse.

Langage formel

Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. La théorie des langages formels a pour objectif de décrire les langages formels. Les mots sont des suites d'éléments de cet alphabet ; les mots qui appartiennent à un langage formel particulier sont parfois appelés mots bien formés ou formules bien formées.

Hiérarchie de Chomsky

Grammaire non contextuelle

En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme où est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par , sans tenir compte du contexte où il apparaît.