Comment démontrer qu'un langage n'est pas régulier ?

L'outil le plus courant est le lemme de pompage, qui stipule que toute chaîne suffisamment longue dans un langage régulier contient une sous-chaîne qui peut être répétée un nombre quelconque de fois tout en restant dans le langage. Trouver une chaîne qui ne peut pas être « pompée » de cette manière prouve que le langage n'est pas régulier ; le théorème de Myhill–Nerode offre un argument alternatif en exhibant une infinité de préfixes distinguables.

Si les automates non déterministes ne sont pas plus puissants, pourquoi les utiliser ?

Ils sont souvent beaucoup plus petits et plus faciles à concevoir ou à dériver d'une expression régulière. La construction par sous-ensembles peut les convertir en forme déterministe si nécessaire, avec un coût potentiellement exponentiel en termes de nombre d'états, de sorte que le non-déterminisme est un outil de spécification pratique plutôt qu'une augmentation de la puissance de reconnaissance.

Automates finis et langages réguliers

Les automates finis sont les machines de calcul les plus simples, lisant une entrée symbole par symbole en utilisant uniquement un nombre borné d'états internes, et les langages qu'ils reconnaissent sont précisément les langages réguliers.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Un automate fini est une machine dotée d'un ensemble fini d'états, d'une fonction de transition sur les symboles d'entrée, d'un état initial et d'états acceptants ; il accepte une chaîne si la lecture de la chaîne le conduit de l'état initial à un état acceptant, et l'ensemble des chaînes acceptées constitue son langage.

Scope

Ce sujet couvre les automates finis déterministes et non déterministes, leur équivalence via la construction par sous-ensembles, les expressions régulières et le théorème de Kleene, le théorème de Myhill–Nerode et la minimisation des états, les propriétés de clôture des langages réguliers, et le lemme de pompage utilisé pour prouver que certains langages ne sont pas réguliers.

Core questions

Quels langages peuvent être reconnus en utilisant uniquement une quantité de mémoire fixe et finie ?
Pourquoi les automates finis déterministes et non déterministes sont-ils également puissants ?
Comment peut-on prouver qu'un langage spécifique n'est pas régulier ?
Quel est le plus petit automate reconnaissant un langage régulier donné ?

Key theories

Construction par sous-ensembles: Tout automate fini non déterministe peut être simulé par un automate déterministe dont les états sont des ensembles des états originaux, prouvant que les deux modèles reconnaissent exactement les mêmes langages.
Théorème de Kleene: Un langage est reconnu par un automate fini si et seulement s'il est décrit par une expression régulière, établissant l'équivalence des descriptions machine et algébrique des langages réguliers.
Théorème de Myhill–Nerode: Un langage est régulier précisément lorsque sa relation d'indistinguabilité de chaînes possède un nombre fini de classes, et ces classes déterminent l'unique automate déterministe minimal pour le langage.

Clinical relevance

Les automates finis sont le moteur de la correspondance d'expressions régulières, des analyseurs lexicaux dans les compilateurs, des fonctions de recherche et remplacement dans les éditeurs de texte, et de la détection de motifs dans les systèmes d'intrusion réseau, où la reconnaissance à mémoire bornée rend le traitement rapide et prévisible.

History

S'appuyant sur le modèle de réseaux neuronaux de McCulloch et Pitts de 1943, Kleene a caractérisé les événements que les automates finis peuvent représenter vers 1951, et Rabin et Scott ont formalisé les automates non déterministes et leurs problèmes de décision en 1959, un travail reconnu plus tard par le prix Turing.

Key figures

Stephen Kleene
Michael Rabin
Dana Scott
Anil Nerode

Seminal works

rabinScott1959
sipser2013

Frequently asked questions

Comment démontrer qu'un langage n'est pas régulier ?: L'outil le plus courant est le lemme de pompage, qui stipule que toute chaîne suffisamment longue dans un langage régulier contient une sous-chaîne qui peut être répétée un nombre quelconque de fois tout en restant dans le langage. Trouver une chaîne qui ne peut pas être « pompée » de cette manière prouve que le langage n'est pas régulier ; le théorème de Myhill–Nerode offre un argument alternatif en exhibant une infinité de préfixes distinguables.
Si les automates non déterministes ne sont pas plus puissants, pourquoi les utiliser ?: Ils sont souvent beaucoup plus petits et plus faciles à concevoir ou à dériver d'une expression régulière. La construction par sous-ensembles peut les convertir en forme déterministe si nécessaire, avec un coût potentiellement exponentiel en termes de nombre d'états, de sorte que le non-déterminisme est un outil de spécification pratique plutôt qu'une augmentation de la puissance de reconnaissance.