L'essentiel à connaître
Un automate fini lit un mot lettre par lettre : il part de son état initial, suit à chaque lettre une transition (une flèche étiquetée par cette lettre) et accepte le mot si la lecture finit dans un état final. Exemple sur l'alphabet $\{a,b\}$ : deux états, $q_0$ (initial et final) et $q_1$ ; la lettre $a$ fait passer de l'un à l'autre, la lettre $b$ ne change rien. Cet automate accepte exactement les mots qui contiennent un nombre pair de $a$, comme $abba$, et refuse $ab$ : cet ensemble de mots est le langage qu'il reconnaît.
Définition : Un automate est déterministe s'il a un seul état initial, aucune transition spontanée (une $\varepsilon$-transition, qui change d'état sans lire de lettre) et, depuis chaque état, au plus une transition par lettre. Il est complet si chaque état a exactement une transition par lettre. Un automate non déterministe peut offrir plusieurs chemins pour un même mot : il l'accepte dès qu'un de ces chemins va d'un état initial à un état final.
La construction des parties transforme un automate non déterministe à $n$ états en un automate déterministe qui reconnaît le même langage : chaque nouvel état est un ensemble d'anciens états, d'où au plus $2^n$ états. Pour reconnaître le complémentaire d'un langage (les mots de l'alphabet qui n'y sont pas), on prend un automate déterministe complet et on échange ses états finaux et non finaux.
Une expression régulière décrit un langage avec $\emptyset$ (le langage vide), $\varepsilon$ (le mot vide), les lettres, l'union $|$ (certains cours écrivent $+$), la concaténation (mots écrits côte à côte) et l'étoile : $L^*$ contient les mots formés de zéro, un ou plusieurs mots de $L$ mis bout à bout, donc toujours $\varepsilon$. Ce sont les notations du programme d'informatique de MPI (2021). Les langages ainsi décrits sont les langages réguliers, qu'on dit aussi rationnels ; tout langage fini en fait partie.
Propriété : Un langage est régulier si et seulement s'il est reconnu par un automate fini (théorème de Kleene). Si $L_1$ et $L_2$ sont réguliers, $L_1 \cup L_2$, $L_1 \cap L_2$ et le complémentaire de $L_1$ le sont aussi.
Avec un nombre fini d'états, un automate ne peut pas compter sans limite : le lemme de l'étoile traduit cette limite.
À retenir : Si $L$ est reconnu par un automate à $n$ états, tout mot $u \in L$ de longueur $|u| \ge n$ s'écrit $u = xyz$ (trois facteurs, c'est-à-dire trois morceaux mis bout à bout) avec $|xy| \le n$, $y \neq \varepsilon$ et $xy^iz \in L$ pour tout entier $i \ge 0$. Ce lemme de l'étoile ne donne qu'une condition nécessaire : il sert à prouver qu'un langage n'est pas régulier, comme $\{a^kb^k \mid k \ge 0\}$, jamais qu'il l'est.
Quiz : teste tes connaissances
Les questions montent en difficulté : les trois dernières sont les plus piégeuses.
Question 1 : Lequel de ces mots l'automate de l'exemple accepte-t-il ?
Réponse : C. $baba$ contient deux $a$ : la lecture passe en $q_1$, puis revient en $q_0$, qui est final. Le piège, c'est $aaab$ : sa longueur est paire, mais il a trois $a$.
Question 2 : Qu'est-ce qui rend un automate non déterministe ?
Réponse : A. Depuis cet état, la même lettre mène à deux endroits : le mot ne fixe plus le chemin. Le piège, c'est B : une transition manquante rend l'automate incomplet, pas non déterministe.
Question 3 : Lequel de ces mots appartient au langage décrit par $(a|b)^*abb$ ?
Réponse : D. L'expression décrit les mots qui finissent par $abb$, avec n'importe quoi devant : $aabb$, c'est $a$ puis $abb$. Le piège, c'est $abbab$ : il contient $abb$, mais pas à la fin.
Question 4 : Quelle expression décrit les mots sur $\{a,b\}$ qui contiennent au moins un $a$ ?
Réponse : B. On coupe le mot juste avant son premier $a$ : des $b$ (peut-être aucun), ce $a$, puis n'importe quoi. Le piège, c'est D : $a(a|b)^*$ oublie les mots qui commencent par $b$, comme $ba$.
Question 5 : Tu déterminises un automate non déterministe à $5$ états par la construction des parties. Combien d'états obtiens-tu au plus ?
Réponse : D. Chaque nouvel état est un ensemble d'anciens états, et $5$ états forment $2^5 = 32$ ensembles, l'ensemble vide compris (il sert d'état puits, d'où l'on ne sort plus). Le piège, c'est $25 = 5^2$ : on ne forme pas des couples d'états, mais des ensembles de toutes tailles.
Question 6 : Un automate déterministe complet reconnaît $L$. Comment reconnaître le complémentaire de $L$ ?
Réponse : A. Chaque mot y est lu jusqu'au bout par un seul chemin : l'échange inverse donc le verdict de chaque mot. Le piège, c'est B : retourner les flèches sert à lire les mots à l'envers, pour obtenir le miroir de $L$, pas son complémentaire.
Question 7 : Quel langage décrit l'expression $\emptyset^*$ ?
Réponse : C. Le cas « zéro mot » de l'étoile donne toujours $\varepsilon$, et $\emptyset$ n'a aucun mot à ajouter. Le piège, c'est A : l'étoile du langage vide n'est pas vide.
Question 8 : Pour prouver que $\{a^kb^k \mid k \ge 0\}$ n'est pas régulier, tu appliques le lemme de l'étoile au mot $u = a^nb^n$, où $n$ est le nombre d'états. Que sais-tu de $y$ ?
Réponse : B. Les $n$ premières lettres de $u$ sont des $a$ et $|xy| \le n$, donc $y$ n'a que des $a$ (au moins un, car $y \neq \varepsilon$). Alors $xy^0z = xz$ a moins de $a$ que de $b$ et sort du langage : contradiction. Le piège, c'est D : la condition $|xy| \le n$ empêche $y$ de déborder sur les $b$.
Question 9 : Lequel de ces langages est régulier ?
Réponse : D. Ce langage est fini ($1\,001$ mots), et tout langage fini est régulier : il suffit d'écrire l'union de ses mots. Le piège, c'est de reconnaître $a^kb^k$ et de répondre « pas régulier » par réflexe : la preuve par le lemme de l'étoile utilise des mots aussi longs qu'on veut, et ici aucun ne dépasse $2\,000$ lettres.
Question 10 : Tous les mots assez longs d'un langage $L$ se découpent comme le dit le lemme de l'étoile. Que peux-tu en conclure ?
Réponse : A. Le lemme dit seulement « régulier $\Rightarrow$ découpage possible » : c'est une condition nécessaire, et des langages non réguliers la vérifient aussi. Le piège, c'est B : conclure « le découpage marche, donc $L$ est régulier », c'est utiliser une réciproque fausse.
Question 11 : Dans un automate non déterministe qui reconnaît $L$, tu échanges états finaux et non finaux. Que reconnaît le nouvel automate ?
Réponse : C. Si l'état initial $q_0$ a deux transitions étiquetées $a$, vers $q_1$ final et vers $q_2$ non final, le mot $a$ est dans $L$ et reste accepté après l'échange, par $q_2$. Le piège, c'est A : la recette de la question 6 exige un automate déterministe complet ; il faut d'abord déterminiser et compléter.
Sources
Ministère de l'Enseignement supérieur, de la Recherche et de l'Innovation, programme d'informatique de la filière MPI, 2021, partie « Langages formels ».
Sandrine Julia, cours « Automates & Langages », licence 3 d'informatique, Université Côte d'Azur.