Corrigé Centrale 2025 Option informatique MP — Partie III, III.2-III.3 (Q27 à Q29) : Élimination des états et automates marqués

Un automate est un quadruplet $\mathcal{A}=(Q,I,T,\Delta )$, avec $I$ les états initiaux, $T$ les états terminaux et $\Delta \subseteq Q\times \Sigma \times Q$ les transitions ; un mot est reconnu s'il étiquette un chemin d'un état initial à un état terminal. Figure 4, l'automate ${\mathcal{A}}_1$ sur ${\Sigma }_3=\{a,b,c\}$ (états initiaux $0$ et $1$, terminal $2$) :

Q27. Appliquer à ${\mathcal{A}}_1$ l'algorithme d'élimination des états, en éliminant $0$, puis $1$, puis $2$ ; en déduire une expression régulière de $\mathcal{L}({\mathcal{A}}_1)$.

Un automate marqué ${\mathcal{A}}^M=(\mathcal{A},M)$ est un automate muni d'un ensemble $M\subseteq \Delta$ de transitions marquées ; il reconnaît les mots qui étiquettent un chemin d'un état initial à un état terminal passant par au moins une transition marquée. Figure 5, ${\mathcal{A}}_2^M$ (initial $0$, terminaux $0$ et $2$, transitions marquées en trait épais mixte, celles d'étiquette $a$), qui reconnaît les mots d'au moins deux lettres commençant et finissant par $a$ ou $b$ et contenant au moins un $a$ :

Construction de $\ddot{\mathcal{A}}$ : on note $\ddot{Q}=\{\ddot{q}\mid q\in Q\}$ une copie de $Q$ ; $\ddot{\mathcal{A}}$ a pour états $\ddot{Q}\cup Q$, pour états initiaux $\ddot{I}=\{\ddot{q}\mid q\in I\}$, pour états terminaux $T$, et pour transitions $\ddot{\Delta }\cup \Delta$, où $\ddot{\Delta }=\{(\ddot{q},x,q^{\prime })\mid (q,x,q^{\prime })\in M\}\cup \{(\ddot{q},x,{\ddot{q}}^{\prime })\mid (q,x,q^{\prime })\in \Delta \setminus M\}$.

Q28. Dessiner l'automate ${\ddot{\mathcal{A}}}_2$ obtenu à partir de ${\mathcal{A}}_2^M$.
Q29. Montrer que $\mathcal{L}({\mathcal{A}}^M)=\mathcal{L}(\ddot{\mathcal{A}})$.