AlgèbreThéorème · Glossaire
théorème de Kleene
En théorie des automates et des langages formels, le théorème de Kleene est un résultat central qui établit l'équivalence entre deux modes de description des langages. Il affirme qu'un langage de mots finis sur un alphabet fini est rationnel — c'est-à-dire qu'il peut être décrit par une expression rationnelle (ou expression régulière) — si et seulement s'il est reconnu par un automate fini. Ce théorème, dû à Stephen Cole Kleene, constitue l'un des fondements de la théorie des langages réguliers et justifie l'interchangeabilité des deux formalismes dans ce cadre.
Sommaire
Ce que vous allez apprendre
- Formuler les deux directions de l’équivalence entre expressions régulières et automates finis.
- Construire et tester un automate à trois états pour les mots terminés par ab.
- Reconnaître les hypothèses du cadre classique et un langage qui exige une mémoire non bornée.
- Distinguer le théorème de Kleene de l’étoile de Kleene et un automate fini d’un langage fini.
- Repérer les extensions logicielles et les coûts de conversion que l’énoncé ne couvre pas.
En clair
Prenons tous les mots formés avec les lettres a et b qui se terminent par ab : ab, aab ou bab en font partie, mais aba n’en fait pas partie. Une expression régulière les décrit d’un seul trait : (a|b)*ab. Un petit automate peut aussi les reconnaître en lisant une lettre après l’autre et en ne mémorisant que la fin utile du mot.
Le théorème de Kleene affirme que ces deux façons de faire ont exactement la même puissance pour les langages réguliers : toute description de l’un des types peut être convertie dans l’autre.
Définition
Un alphabet fini, noté Σ, est un ensemble de symboles. Un mot est une suite finie de symboles de Σ, et un langage L est un ensemble de tels mots. Une expression rationnelle, aussi appelée expression régulière, construit un langage à partir de symboles, du langage vide et du mot vide, au moyen de l’union, de la concaténation et de l’étoile de Kleene. Cette étoile autorise un nombre fini quelconque de répétitions, y compris zéro.
Un automate fini possède un nombre fini d’états. Il lit le mot de gauche à droite, change d’état selon le symbole rencontré et accepte le mot si la lecture se termine dans un état final. Dans le cadre classique des mots finis sur Σ, le théorème de Kleene donne l’équivalence suivante, où E désigne une expression régulière et A un automate fini :
L’expression donne une description déclarative des mots permis ; l’automate fournit une procédure de reconnaissance. L’équivalence concerne les langages reconnus, pas la taille des deux descriptions ni la facilité de leur conversion.
Le principe
Soit L un langage de mots finis sur un alphabet fini. Si L est décrit par une expression régulière, alors il existe un automate fini qui reconnaît exactement L. Réciproquement, si un automate fini reconnaît L, alors il existe une expression régulière qui décrit exactement L.
La première direction se prouve en construisant des automates pour les expressions élémentaires, puis en préservant l’union, la concaténation et l’étoile. La direction inverse élimine progressivement les états d’un automate tout en étiquetant les chemins par des expressions régulières.
Quand l'utiliser
Le cadre usuel comporte un alphabet fini, des mots de longueur finie et les opérations rationnelles classiques : union, concaténation et étoile. Du côté automate, la mémoire doit se réduire à un ensemble fini d’états. L’automate peut être déterministe ou non déterministe, avec transitions spontanées selon la construction choisie : ces variantes reconnaissent la même classe de langages.
Un contre-cas apparaît avec le langage des mots anbn, pour un entier n ≥ 0 : reconnaître exactement autant de a que de b exige de retenir une quantité non bornée. Aucun automate fini ni aucune expression régulière classique ne le décrit. Une grammaire algébrique ou un automate à pile fournit alors un modèle adapté.
Un exemple, pas à pas
Données. L’alphabet est {a, b}. Le langage L contient exactement les mots qui se terminent par ab. L’expression régulière choisie est (a|b)*ab. L’automate comporte l’état initial q0, l’état q1 qui mémorise un dernier a, et l’état final q2 qui mémorise la terminaison ab.
1. Depuis q0, lire a mène à q1, tandis que lire b laisse en q0.
2. Depuis q1, lire a laisse en q1 et lire b mène à l’état final q2. Depuis q2, lire a ramène à q1 et lire b à q0.
3. Pour le mot baab, le parcours est q0 → q0 → q1 → q1 → q2. Le dernier état est final : baab est accepté et se termine bien par ab.
4. Pour le mot aba, le parcours finit en q1. Ce mot est refusé, conformément à l’expression, car sa fin est ba et non ab.
Contrôle. Dans le diagramme de l’automate, toute transition arrivant en q2 lit b depuis q1 : un mot est donc accepté exactement lorsque ses deux dernières lettres sont ab.
En pratique
Pour chercher une forme dans du texte, l’expression régulière est souvent la description la plus compacte. Si l’on doit ensuite analyser un long flux caractère par caractère, sa conversion en automate donne un état courant et une décision d’acceptation à la fin.
Pour concevoir un analyseur lexical, des expressions décrivent les identifiants, nombres ou séparateurs. Un automate est préférable pendant l’exécution lorsque chaque nouveau caractère doit déclencher une transition déterminée.
Pour démontrer qu’un langage est régulier, on choisit la représentation la plus maniable : fournir une expression ou construire un automate suffit grâce au théorème. Si le langage exige une mémoire non bornée, comme compter exactement autant de a que de b, il faut changer de modèle.
À ne pas confondre
Théorème de Kleene et étoile de Kleene. L’étoile est une opération : appliquée à un langage, elle forme tous les assemblages finis de ses mots, y compris l’assemblage vide. Le théorème est le résultat d’équivalence entre expressions régulières et automates finis. Dans (a|b)*ab, le symbole * est l’étoile ; l’équivalence avec l’automate relève du théorème.
Automate fini et langage fini. Le mot « fini » qualifie le nombre d’états de l’automate, pas nécessairement le nombre de mots acceptés. L’automate de l’exemple n’a que trois états, mais il accepte une infinité de mots, dont ab, aab, bab et aaab.
Limites et pièges
Extensions des logiciels. Certaines syntaxes appelées « expressions régulières » ajoutent des références arrière ou d’autres mécanismes qui dépassent les opérations rationnelles classiques. Si un motif dépend de ce type d’extension, le théorème ne garantit plus sa traduction en automate fini ; il faut examiner la fonctionnalité réellement utilisée.
Équivalence sans compacité garantie. Deux descriptions peuvent reconnaître le même langage tout en ayant des tailles très différentes. Le passage d’un automate non déterministe à un automate déterministe peut, dans le pire cas, faire passer de n états à 2n états. Il faut donc distinguer existence d’une conversion et coût de la représentation obtenue.
Mot vide. L’étoile autorise zéro répétition : le mot vide appartient toujours au langage R* obtenu à partir d’un langage R. En revanche, (a|b)*ab ne contient pas le mot vide, car le suffixe ab reste obligatoire. Il faut vérifier l’expression entière, pas seulement la présence d’une étoile.
Cadre des mots finis. L’énoncé présenté ne traite ni les mots infinis ni les calculs généraux d’un programme. Pour ces objets, d’autres modèles et d’autres notions d’acceptation sont nécessaires ; l’équivalence classique ne doit pas être transposée sans préciser ce nouveau cadre.
Pour aller plus loin
automate — Préciser les états, transitions et critères d’acceptation qui rendent opérationnel le versant reconnaissance du théorème.
Langages formels et automates — Replacer l’équivalence de Kleene dans le cadre général qui relie descriptions syntaxiques et machines de reconnaissance.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres