Corrigé Centrale 2026 Option informatique MP — Partie A (Q1 à Q8) : Coloration syntaxique : automates et analyse lexicale

Q1. L'expression régulière

$$e=0\mid 1(0\mid 1{)}^{\ast }$$

convient : le premier membre dénote le seul mot $0$, le second exactement les mots dont la première lettre est $1$, suivie d'un mot quelconque de ${\Sigma }^{\ast }$. L'union des deux est le langage demandé ; les deux membres sont disjoints, ce qui assure qu'aucune écriture n'a de zéro de tête superflu (le mot $01$ n'est dénoté ni par l'un ni par l'autre).

Q2. On prend trois états : $q_0$ initial, $q_z$ (on a lu exactement $0$) et $q_1$ (on a lu $1$ puis n'importe quoi), $q_z$ et $q_1$ acceptants :

Il est déterministe : de chaque état part au plus une transition par lettre (on peut le compléter par un état puits non acceptant recevant les transitions manquantes, par exemple $q_z\stackrel{0,1}{\to }$ puits). Un mot est accepté ssi il vaut $0$ (arrêt en $q_z$ ; toute lettre supplémentaire bloque) ou commence par $1$ (on reste ensuite en $q_1$) : c'est le langage de Q1.

Base 10 : on remplace l'alphabet par $\{0,\dots ,9\}$, l'étiquette $1$ de $q_0\to q_1$ par $1,2,\dots ,9$ et la boucle sur $q_1$ par $0,1,\dots ,9$ ; la transition $q_0\stackrel{0}{\to }{q}_z$ ne change pas. On reconnaît alors $0\mid (1\mid \cdots \mid 9)(0\mid \cdots \mid 9{)}^{\ast }$.

Q3. Un mot est accepté ssi il existe un calcul de $1$ à $4$ : on boucle en $1$ sur un préfixe $u$, on lit $l$, $e$, $t$, puis on boucle en $4$ sur un suffixe $v$. Donc

$$\mathcal{L}(A_l)={\Sigma }^{\ast }\mathrm{let}{\Sigma }^{\ast },$$

l'ensemble des mots qui contiennent le facteur let ($\Sigma$ désigne ici l'alphabet des caractères, qui contient $l$, $e$, $t$). Un automate déterministe (complet) mémorise le plus long suffixe du mot lu qui est préfixe de let : état $0$ (aucun), $1$ (l), $2$ (le), $3$ (facteur let déjà vu, puits acceptant). Sur le dessin, « autre » désigne toute lettre non écrite sur une autre flèche sortant du même état :

Depuis l'état $2$, lire l ramène en $1$ (et non en $0$) : le suffixe l de lel peut commencer une occurrence. Par récurrence sur la longueur du mot lu, l'état atteint est le plus long suffixe préfixe de let tant que let n'est pas apparu, et $3$ ensuite ; le mot est donc accepté ssi il contient let. (Vérifié en OCaml contre la définition sur tous les mots de longueur au plus $7$ sur $\{l,e,t,a\}$.)