Corrigé Centrale 2025 Option informatique MP — Partie III, III.4 (Q30 à Q34) : Automate des minimaux d'un langage régulier

Q30. Pour $u\in L$, $u$ est minimal ssi aucun $v\in L$ ne vérifie $v\prec u$, c'est-à-dire ssi $u\notin \breve{L}$ (car $u\in {\Sigma }^{+}$). Donc

$$\min (L)=L\setminus \breve{L}=L\cap ({\Sigma }^{\ast }\setminus \breve{L}).$$

L'ensemble des langages réguliers est stable par complémentaire et par intersection : si $\breve{L}$ est régulier, ${\Sigma }^{\ast }\setminus \breve{L}$ l'est, puis $\min (L)$, intersection de deux langages réguliers, l'est aussi.

Remarque utilisée ensuite : comme $\epsilon \notin L=\mathcal{L}(\mathcal{A})$, aucun état initial de $\mathcal{A}$ n'est terminal ($I\cap T=\varnothing$), sinon le chemin vide reconnaîtrait $\epsilon$.

Q31. Pour ${\mathcal{A}}_1$ : $T=\{2\}$, $\Delta =\{(0,c,1),(1,a,2),(2,c,1)\}$.

• (a) On supprime $(2,c,1)$, qui sort de l'état terminal $2$ : ${\Delta }^{\prime }=\{(0,c,1),(1,a,2)\}$.
• (b) Aucune lettre n'est strictement supérieure à $c$ : $(0,c,1)$ ne produit rien. Pour $(1,a,2)$, les lettres $b$ et $c$ donnent $M^{\prime }=\{(1,b,2),(1,c,2)\}$.
• (c) $M^{\prime \prime }=\{(2,a,2),(2,b,2),(2,c,2)\}$.

D'où l'automate marqué ci-dessous (états initiaux $0$ et $1$, terminal $2$, transitions marquées en trait épais mixte) :

Contrôle : $\mathcal{L}({\mathcal{A}}_1)=(\epsilon \mid c)a(ca{)}^{\ast }$ (Q27) ; l'automate marqué reconnaît $(\epsilon \mid c)(a{\Sigma }_3^{+}\mid (b\mid c){\Sigma }_3^{\ast })$, et une énumération de tous les mots de longueur au plus $12$ montre que c'est bien $\breve{L}$ (ces mots sont strictement au-dessus de $a$ ou de $ca$).