La hiérarchie de Chomsky

La hiérarchie de Chomsky organise les langages formels en quatre classes imbriquées, chacune définie par une restriction sur les règles de grammaire et associée à un type distinct de machine abstraite.

Definition

La hiérarchie de Chomsky est une classification des grammaires formelles par des restrictions progressivement plus fortes sur leurs règles de production, produisant les classes de langages réguliers, hors contexte, contextuels et récursivement énumérables dans une chaîne d'inclusions strictes.

Scope

Ce sujet couvre les quatre types de grammaires — non restreintes, contextuelles, hors contexte et régulières — leur inclusion stricte, et le modèle d'automate correspondant à chaque niveau, à savoir la machine de Turing, l'automate linéairement borné, l'automate à pile et l'automate fini, ainsi que les propriétés de clôture et de décidabilité qui séparent les niveaux.

Core questions

• Comment les restrictions sur les règles de grammaire se traduisent-elles en limites de mémoire et de puissance de calcul ?
• Pourquoi chaque niveau de la hiérarchie est-il strictement contenu dans le suivant ?
• Quel modèle d'automate correspond à chaque type de grammaire ?
• Comment les propriétés de décidabilité et de clôture évoluent-elles à mesure que l'on monte dans la hiérarchie ?

Key theories

Correspondance grammaire-machine

Chaque classe de grammaire est reconnue par un modèle de machine spécifique — les grammaires régulières par les automates finis, les grammaires hors contexte par les automates à pile, les grammaires contextuelles par les automates linéairement bornés, et les grammaires non restreintes par les machines de Turing — reliant les descriptions génératives et opérationnelles du calcul.

Inclusion stricte des classes de langages

Chaque niveau contient proprement celui qui le précède, comme en témoignent des langages séparateurs concrets, de sorte que la hiérarchie est une véritable échelle de puissance expressive croissante plutôt qu'une collection de descriptions équivalentes.

Clinical relevance

La hiérarchie constitue la carte organisatrice de la théorie des langages formels : elle indique aux concepteurs de langages de programmation, de langages de requête et de spécifications de protocoles la quantité de mécanismes requise par une classe donnée de motifs, et elle délimite la frontière entre ce qui est décidable et ce qui est seulement reconnaissable.

History

Chomsky a proposé cette hiérarchie à la fin des années 1950 alors qu'il recherchait des modèles formels de la syntaxe des langues naturelles, et les correspondances avec les machines ont été établies à mesure que la théorie des automates mûrissait dans les années 1960, avec l'introduction des automates linéairement bornés par Myhill et la clarification du niveau contextuel par Kuroda.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

Quels sont les quatre niveaux de la hiérarchie de Chomsky ?

Du moins au plus puissant, ce sont les langages réguliers (Type 3), les langages hors contexte (Type 2), les langages contextuels (Type 1) et les langages récursivement énumérables (Type 0). Chaque niveau assouplit les restrictions sur les règles de grammaire et correspond à une machine dotée de plus de mémoire.

Le langage naturel est-il couvert par la hiérarchie de Chomsky ?

La hiérarchie était initialement motivée par la linguistique, mais la plupart des linguistes concluent que les langues naturelles ne sont pas hors contexte, se situant à un niveau souvent qualifié de légèrement contextuel. La hiérarchie reste fondamentale en informatique même si le langage humain ne s'y conforme que de manière lâche.