Langages réguliers et automates finis

Cours complet · informatique (MP2I/MPI), chapitre 29 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

29.1 Deux façons de décrire un même ensemble de mots

Le programme introduit les expressions régulières « comme formalisme dénotationnel pour spécifier un motif », et les automates « comme un formalisme opérationnel efficace pour la recherche de motifs ». Ces deux mots portent tout le chapitre :

	Expression régulière	Automate
Ce qu'elle dit	quoi : à quoi ressemble un mot	comment : on le lit lettre à lettre
Nature	déclarative	opérationnelle
Ce qu'on en fait	on l'écrit	on l'exécute

Et le théorème de Kleene dira que les deux décrivent exactement les mêmes ensembles de mots. C'est ce qui permet d'écrire un motif de façon commode et de le chercher de façon efficace.

29.2 Langages

Définition 29.1Alphabet, mot, langage

Un alphabet $Σ$ est un ensemble fini de lettres. Un mot est une suite finie de lettres ; le mot vide se note $ε$ . L'ensemble de tous les mots est $Σ^{*}$ , et un langage est une partie de $Σ^{*}$ .

Le vocabulaire préfixe / suffixe / facteur / sous-mot est celui du chapitre chap:textes.

Définition 29.2Les trois opérations régulières

Pour deux langages $L$ et $M$ :

union : $L \cup M$ ;
concaténation : $L M = {uv : u \in L, v \in M}$ ;
étoile de Kleene : $L^{*} = {ε} \cup L \cup LL \cup LLL \cup \dots$ , les concaténations d'un nombre quelconque, éventuellement nul, de mots de $L$ .

Définition 29.3Langages réguliers, par induction

L'ensemble des langages réguliers sur $Σ$ est le plus petit ensemble tel que :

$\emptyset { ε } \frac{a \in Σ}{{ a }} \frac{L , M}{L \cup M} \frac{L , M}{L M} \frac{L}{L ^{*}}$

C'est encore un ensemble inductif au sens du chapitre chap:induction : les preuves sur les langages réguliers se font par induction sur cette construction.

Définition 29.4Expression régulière

Une expression régulière est une écriture qui dénote un langage régulier. Le programme fixe les notations : $\emptyset$ pour le langage vide, $ε$ pour le langage réduit au mot vide, $∣$ pour l'union, la juxtaposition pour la concaténation, l'étoile pour Kleene.

Expression	Langage dénoté
$ab$	le seul mot `ab`
$a ∣ b$	les deux mots `a` et `b`
$a^{*}$	$ε$ , `a`, `aa`, `aaa`, …
$(a ∣ b)^{*} a$	tous les mots se terminant par `a`
$a (a ∣ b)^{*}$	tous les mots commençant par `a`

AttentionL'expression est une écriture, le langage est un ensemble

C'est la distinction syntaxe / sémantique, pour la troisième fois du livre. $(a ∣ b)^{*}$ et $(b ∣ a)^{*}$ sont deux expressions différentes qui dénotent le même langage — exactement comme $p \land q$ et $q \land p$ sont deux formules distinctes et équivalentes.

iRemarqueExpressions régulières étendues

Le programme demande de faire « le lien avec les expressions régulières de la norme posix », en précisant qu'« on ne développe aucune théorie supplémentaire à leur sujet et aucune connaissance au sujet de cette norme n'est exigible ». Les raccourcis courants — + pour « au moins un », ? pour « zéro ou un », les classes [a-z] — n'ajoutent aucune expressivité : ils s'écrivent avec les trois opérations de base.

29.3 Automates finis

Définition 29.5Automate fini déterministe

Un automate fini déterministe est un quintuplet $(Q, Σ, δ, q_{0}, F)$ : un ensemble fini d'états, un alphabet, une fonction de transition $δ : Q \times Σ \to Q$ , un état initial et un ensemble d'états acceptants.

Un mot est reconnu si, lu lettre à lettre depuis $q_{0}$ , il mène à un état acceptant. Le langage reconnu est l'ensemble de ces mots.


/* Vrai si l'automate reconnaît le mot. delta[q][c] est l'état atteint.
   Précondition : mot terminé par '\0'. Complexité : Theta(|mot|). */
bool reconnait(int delta[][ALPHABET], const bool acceptant[],
               int q0, const char mot[]) {
    int q = q0;
    for (int i = 0; mot[i] != '\0'; i = i + 1) { q = delta[q][(int) mot[i]]; }
    return acceptant[q];
}

ImportantLe coût : linéaire, et indépendant de la taille du motif

Un automate lit le mot une fois, une lettre à la fois, en $O (1)$ par lettre. Il ne revient jamais en arrière et n'occupe aucune mémoire hors son état courant.

C'est ce qui en fait l'outil de la recherche de motifs : le coût est $Θ (n)$ quelle que soit la complexité de l'expression cherchée. Comparé à Boyer-Moore ou Rabin-Karp du chapitre chap:textes, l'automate est plus général — il cherche un motif, pas un mot fixé — pour le même coût asymptotique.

Définition 29.6Accessible, co-accessible, émondé

Un état est accessible s'il est atteint depuis $q_{0}$ par un mot, co-accessible s'il mène à un état acceptant. Un automate est émondé si tous ses états sont accessibles et co-accessibles.

Émonder revient à deux parcours de graphe (chapitre chap:parcours) : un depuis $q_{0}$ dans l'automate, un depuis $F$ dans l'automate transposé. C'est exactement la manipulation du chapitre chap:graphes-avances.

29.3.1 Non-déterminisme

Définition 29.7Automate non déterministe

Un automate fini non déterministe autorise plusieurs transitions pour une même lettre — $δ : Q \times Σ \to P (Q)$ — et des transitions spontanées ( $ε$ -transitions), franchies sans lire de lettre. Un mot est reconnu s'il existe un chemin acceptant.

ImportantLe non-déterminisme n'ajoute aucune puissance, seulement de la concision

C'est le résultat central de la section. Un automate non déterministe se déterminise : ses états deviennent des ensembles d'états de l'original.

$Δ (S, a) = q \in S ⋃ δ (q, a), S acceptant ⟺ S \cap F \neq = \emptyset .$

L'automate obtenu reconnaît le même langage. Son nombre d'états peut valoir $2^{∣ Q ∣}$ — et cette explosion est parfois inévitable.

Le prix du déterminisme est donc la taille, pas l'expressivité. On écrit un automate non déterministe parce qu'il est petit et lisible ; on le détermine pour l'exécuter vite.

iRemarqueÉliminer les transitions spontanées

Le programme demande de « faire le lien entre l'élimination des transitions spontanées et l'accessibilité dans un graphe » : la clôture d'un état par $ε$ est l'ensemble des états qu'il atteint en ne suivant que des $ε$ -transitions — un simple parcours. On remplace ensuite chaque transition par sa version close.

Le programme borne l'exigence : « on aborde … les constructions d'automates à la Thompson sur des exemples, sans chercher à formaliser complètement les algorithmes sous-jacents ».

29.4 Le théorème de Kleene

◆Théorème 29.8Kleene

Un langage est régulier si et seulement s'il est reconnu par un automate fini.

29.4.1 Sens direct : de l'expression à l'automate

Méthode : Berry-Sethi, ou l'automate de Glushkov

Le programme demande cette construction précise : « construction de l'automate de Glushkov associé à une expression régulière par l'algorithme de Berry-Sethi ». Et il en donne la clé : « les notions de langage local et d'expression régulière linéaire sont introduites dans cette seule perspective ».

L'idée. On numérote toutes les occurrences de lettres de l'expression, ce qui la rend linéaire — chaque lettre y figure une seule fois. Sur $(a ∣ b)^{*} ab$ :

$(a_{1} ∣ b_{2})^{*} a_{3} b_{4} .$

Un langage dont l'expression est linéaire est local : il est entièrement déterminé par trois ensembles finis, qui se calculent par induction sur l'expression :

$P$	les lettres qui peuvent commencer un mot : ${a_{1}, b_{2}, a_{3}}$
$D$	les lettres qui peuvent terminer un mot : ${b_{4}}$
$F$	les facteurs de deux lettres autorisés : $a_{1} a_{1}, a_{1} b_{2}, a_{1} a_{3}, \dots, a_{3} b_{4}$

L'automate a alors un état par lettre numérotée, plus un état initial. On va de $x$ à $y$ par la lettre de $y$ si $x y \in F$ ; l'initial mène à chaque lettre de $P$ ; les acceptants sont les lettres de $D$ .

Deux propriétés remarquables : l'automate obtenu a exactement $∣ lettres ∣ + 1$ états — jamais plus —, et il n'a aucune transition spontanée.

29.4.2 Sens réciproque : de l'automate à l'expression

Méthode : Élimination des états

Le programme le dit : « on se limite à la description du procédé d'élimination et à sa mise en œuvre sur des exemples d'automates de petite taille ; cela constitue la preuve du sens réciproque du théorème de Kleene ».

On autorise les transitions à porter des expressions régulières au lieu de lettres, puis on retire les états un à un. En retirant $q$ , toute paire $(p, r)$ de voisins reçoit une transition qui résume les chemins passant par $q$ :

$p E_{pq} E_{q q}^{*} E_{q r} r,$

où $E_{q q}$ dénote les boucles sur $q$ — d'où l'étoile. À la fin, il ne reste que l'initial et un acceptant, et l'expression portée par la transition qui les joint dénote le langage.

29.5 Propriétés de clôture

◆Théorème 29.9Stabilité

La classe des langages reconnaissables est stable par union finie, intersection finie et complémentaire.

Démonstration (Constructive, et c'est l'intérêt)

Complémentaire : sur un automate déterministe et complet, il suffit d'échanger les états acceptants et non acceptants.

Intersection : le produit de deux automates. Les états sont les couples $(q, q^{'})$ , la transition agit sur les deux composantes à la fois, et le couple est acceptant si les deux le sont. Pour l'union, on demande qu'au moins un le soit.

AttentionLe complémentaire exige le déterminisme, et c'est un piège

Échanger les états acceptants d'un automate non déterministe ne donne pas le complémentaire. Un mot peut avoir à la fois un chemin acceptant et un chemin refusant : après échange, il reste reconnu. Il faut déterminiser d'abord — au prix, éventuellement, d'une explosion exponentielle du nombre d'états.

29.6 Le lemme de l'étoile

◆Théorème 29.10Lemme de l'étoile

Soit $L$ reconnu par un automate à $n$ états. Pour tout $u \in L$ tel que $∣ u ∣ \geq n$ , il existe une décomposition $u = x y z$ telle que

$∣ x y ∣ \leq n, y \neq = ε, x y^{*} z \subseteq L .$

Démonstration

La lecture de $u$ passe par $∣ u ∣ + 1 \geq n + 1$ états. L'automate n'en ayant que $n$ , deux d'entre eux coïncident parmi les $n + 1$ premiers : c'est le principe des tiroirs. Soit $q$ cet état répété, atteint après $x$ puis après $x y$ , avec $∣ x y ∣ \leq n$ et $y \neq = ε$ .

Le chemin qui lit $y$ est donc un circuit sur $q$ . On peut le parcourir zéro fois, une fois, ou autant qu'on veut : tous les mots $x y^{k} z$ mènent au même état final, et sont donc reconnus.

ImportantSon usage : montrer qu'un langage n'est PAS régulier

Le lemme s'emploie par contraposée. Pour $L = {a^{k} b^{k} : k \geq 0}$ :

Supposons $L$ reconnu par un automate à $n$ états, et prenons $u = a^{n} b^{n}$ . Comme $∣ x y ∣ \leq n$ , le facteur $y$ est composé uniquement de $a$ , et $y \neq = ε$ . Alors $x y^{2} z$ contient plus de $a$ que de $b$ : il n'est pas dans $L$ . Contradiction.

L'interprétation vaut d'être retenue : un automate fini a une mémoire bornée — son état. Il ne peut pas compter jusqu'à un entier arbitraire, donc pas vérifier qu'il y a autant de $a$ que de $b$ . C'est précisément cette limite que le chapitre chap:grammaires lèvera.

29.7 Ce qu'il faut retenir

ImportantLangages réguliers : six points

Une expression régulière dit quoi (déclaratif), un automate dit comment (opérationnel). Kleene : ils décrivent les mêmes langages.
Un automate déterministe reconnaît en $Θ (n)$ , avec pour seule mémoire son état courant.
Le non-déterminisme n'ajoute pas d'expressivité : il se détermine, au prix d'un nombre d'états jusqu'à $2^{∣ Q ∣}$ . Petit et lisible d'un côté, rapide de l'autre.
Berry-Sethi : numéroter les lettres rend l'expression linéaire, donc le langage local ; l'automate a alors un état par lettre et aucune transition spontanée.
Les reconnaissables sont clos par union, intersection et complémentaire — mais le complémentaire exige de déterminiser d'abord.
Le lemme de l'étoile sert à réfuter. Sa cause tient en une phrase : un automate fini n'a qu'une mémoire bornée.

Continuer sur Adloun : animation, QCM, fiches, exercices