Théorie des langages formels et des automates

La théorie des langages formels et des machines abstraites qui les reconnaissent, fournissant le vocabulaire pour décrire la complexité d'un motif linguistique et les algorithmes capables de le traiter.

Definition

La théorie des langages formels étudie les ensembles de chaînes définis par des grammaires, et la théorie des automates étudie les machines abstraites qui décident de l'appartenance à ces ensembles.

Scope

Couvre la hiérarchie de Chomsky (langages réguliers, hors contexte, sensibles au contexte, récursivement énumérables), les grammaires correspondantes et les automates de reconnaissance — machines à états finis, automates à pile et machines de Turing. Elle aborde les propriétés de clôture et de décidabilité pertinentes pour le traitement du langage et la question de la place du langage naturel dans cette hiérarchie. Les lemmes de pompage et les preuves complètes de complexité sont traités comme des éléments de contexte plutôt que comme du contenu principal.

Core questions

• Quel automate correspond à chaque niveau de la hiérarchie de Chomsky ?
• Où se situe le langage naturel dans la hiérarchie, et pourquoi est-il avancé qu'il dépasse la puissance des langages hors contexte ?
• Que signifie pour une classe de langages d'être fermée sous une opération, et pourquoi cela est-il important pour l'ingénierie ?

Key concepts

• langage régulier
• grammaire hors contexte
• grammaire sensible au contexte
• automate à états finis
• automate à pile
• machine de Turing
• propriétés de clôture
• sensibilité au contexte légère

Key theories

Hiérarchie de Chomsky

Quatre classes imbriquées de langages formels, chacune générée par un type de grammaire restreint et reconnue par un automate correspondant, ordonnant les constructions linguistiques selon la puissance de calcul requise.

Correspondance grammaire-automate

Chaque classe de grammaire est prouvablement équivalente à une classe de machines — les grammaires régulières aux automates finis, les grammaires hors contexte aux automates à pile — reliant les descriptions génératives aux algorithmes de reconnaissance.

History

L'article de Chomsky de 1956 a introduit la hiérarchie dans le cadre d'un argument selon lequel les modèles à états finis étaient inadéquats pour le langage naturel. Les décennies suivantes ont formalisé les correspondances entre automates, et les linguistes computationnels ont montré par la suite que le langage naturel ne nécessite au plus qu'une puissance 'légèrement sensible au contexte' (mildly context-sensitive), motivant ainsi des formalismes grammaticaux au-delà des grammaires hors contexte.

Debates

Le langage naturel est-il hors contexte ?

Des dépendances croisées (cross-serial dependencies) dans des langues comme le suisse allemand ont été utilisées pour soutenir que le langage naturel dépasse la puissance des langages hors contexte, menant à la notion de sensibilité au contexte légère (mild context-sensitivity) comme le bon niveau d'expressivité.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

Quelle est la différence entre un langage régulier et un langage hors contexte ?

Les langages réguliers peuvent être reconnus avec une mémoire finie par un automate à états finis ; les langages hors contexte peuvent nécessiter une pile (un automate à pile) pour suivre une structure imbriquée, telle que des parenthèses équilibrées ou des propositions enchâssées.