Pourquoi un automate fini ne peut-il pas reconnaître les parenthèses équilibrées ?

Reconnaître une imbrication arbitrairement profonde nécessite de compter le nombre d'ouvertures non encore appariées, ce qui peut dépasser tout nombre fixe d'états. Un automate fini ne dispose que d'une mémoire bornée ; cette capacité de comptage se situe donc à un niveau supérieur, avec les automates à pile et les langages hors contexte (context-free).

Quel est l'intérêt pratique de la théorie des langages formels ?

Elle indique aux ingénieurs quels motifs un outil donné peut exprimer. Les expressions régulières suffisent pour les lexèmes (tokens) mais pas pour les structures imbriquées, c'est pourquoi les compilateurs répartissent le travail entre un analyseur lexical (lexer) régulier et un analyseur syntaxique (parser) hors contexte (context-free), et pourquoi les outils de vérification s'appuient sur des automates sur mots infinis.

Automates et langages formels

La théorie des automates et des langages formels étudie des machines idéalisées de puissance croissante et les classes de chaînes de caractères, ou langages, que chacune peut reconnaître, offrant une description mathématique précise de ce qui constitue un motif et de ce qu'il faut pour le détecter.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Un langage formel est un ensemble de chaînes finies sur un alphabet fixe, et un automate est un dispositif de calcul abstrait dont les calculs acceptants définissent un tel langage ; ce domaine classe les langages selon le type d'automate ou de grammaire le plus simple qui les génère ou les reconnaît.

Scope

Ce domaine couvre les automates finis et les langages réguliers, les automates à pile et les langages hors contexte (ou context-free), la hiérarchie de Chomsky reliant les grammaires aux modèles de machines, les propriétés de clôture et de décidabilité des classes de langages, ainsi que les automates qui traitent les mots infinis et les arbres, accompagnés de leurs caractérisations algébriques et logiques.

Sub-topics

Core questions

Quels langages une machine à mémoire finie peut-elle reconnaître, et lesquels ne le peut-elle pas ?
Comment les grammaires et les modèles de machines correspondent-ils aux différents niveaux de la hiérarchie de Chomsky ?
Quelles questions concernant une classe de langages, telles que la vacuité ou l'équivalence, sont algorithmiquement décidables ?
Comment les automates s'étendent-ils aux mots infinis et aux arbres, et pourquoi cela est-il important pour la vérification ?

Key theories

Équivalence des automates finis déterministes et non déterministes: Tout automate fini non déterministe peut être converti, par la construction par sous-ensembles, en un automate déterministe acceptant le même langage ; ainsi, le non-déterminisme n'ajoute aucune puissance de reconnaissance au niveau des automates finis, même s'il peut être exponentiellement plus concis.
Théorème de Kleene: Les langages reconnus par les automates finis sont exactement les langages réguliers décrits par les expressions régulières, reliant ainsi les vues machine, algébrique et grammaticale de la classe de langages la plus simple.
La hiérarchie de Chomsky: Les langages réguliers, hors contexte (context-free), contextuels (context-sensitive) et récursivement énumérables forment une chaîne d'inclusion stricte, chaque niveau étant associé à un type de grammaire et à un modèle d'automate doté d'une structure de mémoire correspondante.

Clinical relevance

Les automates finis et les expressions régulières sont à la base de l'analyse lexicale dans les compilateurs, la recherche de texte et la spécification de protocoles, tandis que les grammaires hors contexte (ou context-free) sous-tendent l'analyse syntaxique des langages de programmation ; les automates sur objets infinis constituent le cœur algorithmique de la vérification de modèles (model checking), où un système est vérifié par rapport à une spécification en logique temporelle.

History

Les modèles à états finis ont émergé des réseaux neuronaux de McCulloch et Pitts dans les années 1940 et ont été formalisés sous une forme théorique des langages par Kleene vers 1951. Rabin et Scott ont introduit les automates non déterministes en 1959, tandis que les grammaires de Chomsky, à partir de la fin des années 1950, ont organisé les classes de langages en la hiérarchie qui structure encore le sujet.

Key figures

Stephen Kleene
Michael Rabin
Dana Scott
Noam Chomsky

Seminal works

rabinScott1959
sipser2013
hopcroft2006

Frequently asked questions

Pourquoi un automate fini ne peut-il pas reconnaître les parenthèses équilibrées ?: Reconnaître une imbrication arbitrairement profonde nécessite de compter le nombre d'ouvertures non encore appariées, ce qui peut dépasser tout nombre fixe d'états. Un automate fini ne dispose que d'une mémoire bornée ; cette capacité de comptage se situe donc à un niveau supérieur, avec les automates à pile et les langages hors contexte (context-free).
Quel est l'intérêt pratique de la théorie des langages formels ?: Elle indique aux ingénieurs quels motifs un outil donné peut exprimer. Les expressions régulières suffisent pour les lexèmes (tokens) mais pas pour les structures imbriquées, c'est pourquoi les compilateurs répartissent le travail entre un analyseur lexical (lexer) régulier et un analyseur syntaxique (parser) hors contexte (context-free), et pourquoi les outils de vérification s'appuient sur des automates sur mots infinis.