Corrigé Mines-Ponts 2026 Informatique option MP — Partie 2 (Q5 à Q14) : Automates sur les vecteurs binaires, déterminisation, produit

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique option MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un automate est un quintuplet $A = (Σ, Q, q_{0}, F, δ)$ avec $δ : Q \times Σ \to P (Q)$ , sans $ε$ -transition ; il est déterministe complet si $∣ δ (q, a) ∣ = 1$ pour tout $(q, a)$ . Dans une lettre de $Σ_{2}$ , la ligne du haut est la ligne 1 ( $v_{1}$ ), celle du bas la ligne 2 ( $v_{2}$ ). Les automates $A_{1}$ et $A_{2}$ du sujet :

Soit $E$ l'ensemble des mots $m$ sur $Σ_{2}$ tels que $v_{2} (m)$ est la plus grande puissance de $2$ qui divise $v_{1} (m)$ . Le type du sujet (états $0, \dots, k - 1$ , l'état initial est toujours $0$ , delta q a est la liste des états de $δ (q, a)$ ) :


type automate = {
    k : int ;
    n : int ;
    finaux : bool array ;
    delta : int -> int array -> int list ;
}

Q5. Démontrer que $L (A_{1}) = E$ . Q6. Montrer que $v_{1} (m) \equiv v_{2} (m) [2 v_{2} (m)]$ pour tout $m \in L (A_{1})$ . Q7. Décrire sans justifier $L (A_{2})$ par une condition sur $v_{1} (m)$ et $v_{2} (m)$ .
Q8. Proposer sans justifier un automate à 3 états reconnaissant $L = {m \in Σ_{3}^{*} ∣ v_{1} (m) = v_{3} (m) ou v_{2} (m) = v_{3} (m)}$ .
Q9. Écrire est_deterministe_complet : automate -> bool en $O (n ∣ Q ∣ ∣ Σ_{n} ∣)$ ; justifier.
Q10. Donner la construction formelle d'un automate déterministe reconnaissant $L (A)$ .
Q11. Écrire union : int array -> automate -> int array -> int array : union etats a lettre renvoie $t$ de taille $k$ avec t.(i)=1 s'il existe $q$ tel que etats.(q)=1 et $q lettre i$ , t.(i)=0 sinon.
Q12. En déduire determinise : automate -> automate (déterministe complet, même langage).
Q13. Écrire complementaire : automate -> automate (langage complémentaire).
Q14. Construire formellement, sur l'ensemble d'états $Q_{1} \times Q_{2}$ , un automate reconnaissant $L (A_{1}) \cap L (A_{2})$ . On dispose ensuite de intersection : automate -> automate -> automate.

Corrigé

Notation : un mot $m$ de longueur $ℓ$ s'écrit $m = m_{0} m_{1} \dots m_{ℓ - 1}$ , et $(π_{i} (m))_{j}$ est la ligne $i$ de la lettre $m_{j}$ ; ainsi $v_{i} (m) = \sum_{j < ℓ} 2^{j} (π_{i} (m))_{j}$ .

Q5. On procède par double inclusion.

$L (A_{1}) \subseteq E$ . L'état $q_{2}$ n'est pas final et n'a aucune transition sortante : un calcul acceptant n'y passe jamais. Un calcul acceptant de $q_{0}$ à $q_{1}$ reste donc un certain nombre $a ⩾ 0$ de fois en $q_{0}$ (boucle $(0 0)$ ), passe en $q_{1}$ par $(1 1)$ , puis boucle en $q_{1}$ . Le mot accepté vérifie donc, pour un $a \in N$ : $m_{j} = (0 0)$ pour $j < a$ , $m_{a} = (1 1)$ , et $m_{j} \in {(0 0), (0 1)}$ pour $a < j < ℓ$ . Alors $π_{2} (m)$ a un seul $1$ , en position $a$ : $v_{2} (m) = 2^{a}$ . Et, en notant $u$ le mot formé par la ligne 1 des lettres $m_{a + 1} \dots m_{ℓ - 1}$ ,

$v_{1} (m) = 2^{a} + j > a \sum 2^{j} (π_{1} (m))_{j} = 2^{a} (1 + 2 v (u)) .$

Donc $2^{a}$ divise $v_{1} (m)$ , et $v_{1} (m) / 2^{a} = 1 + 2 v (u)$ est impair : $2^{a + 1}$ ne divise pas $v_{1} (m)$ . Comme $v_{1} (m) \neq = 0$ , la plus grande puissance de $2$ divisant $v_{1} (m)$ est $2^{a} = v_{2} (m)$ : $m \in E$ .

$E \subseteq L (A_{1})$ . Soit $m \in E$ de longueur $ℓ$ . Nécessairement $v_{1} (m) \neq = 0$ (tout $2^{b}$ divise $0$ : il n'y aurait pas de plus grande puissance), et $v_{2} (m) = 2^{a}$ pour un $a \in N$ . Par unicité de l'écriture binaire (Q3), $2^{a} = v_{2} (m) < 2^{ℓ}$ impose $a < ℓ$ et $π_{2} (m)$ a un unique $1$ , en position $a$ . Ensuite, $\sum_{j < a} 2^{j} (π_{1} (m))_{j}$ est le reste de $v_{1} (m)$ modulo $2^{a}$ ; il est nul car $2^{a} ∣ v_{1} (m)$ , donc $(π_{1} (m))_{j} = 0$ pour $j < a$ . De même le reste modulo $2^{a + 1}$ vaut $2^{a} (π_{1} (m))_{a}$ et n'est pas nul car $2^{a + 1} ∤ v_{1} (m)$ : $(π_{1} (m))_{a} = 1$ . Ainsi $m_{j} = (0 0)$ pour $j < a$ , $m_{a} = (1 1)$ , et $m_{j} \in {(0 0), (0 1)}$ pour $j > a$ (ligne 2 nulle). Le calcul qui boucle $a$ fois en $q_{0}$ , passe en $q_{1}$ par $m_{a}$ puis boucle en $q_{1}$ existe et s'achève dans l'état final $q_{1}$ : $m \in L (A_{1})$ .

(Contrôle exécuté : pour tous les mots de longueur $⩽ 7$ sur $Σ_{2}$ , soit $21845$ mots, l'appartenance à $L (A_{1})$ coïncide avec l'appartenance à $E$ .)

Q6. D'après Q5, $m \in L (A_{1})$ donne $v_{2} (m) = 2^{a}$ et $v_{1} (m) = 2^{a} + 2^{a + 1} v (u)$ , d'où $v_{1} (m) - v_{2} (m) = 2 v_{2} (m) v (u)$ : c'est un multiple de $2 v_{2} (m)$ , donc $v_{1} (m) \equiv v_{2} (m) [2 v_{2} (m)]$ .

Q7. $L (A_{2}) = {m \in Σ_{2}^{*} ∣ v_{1} (m) > v_{2} (m)}$ . (L'état courant indique lequel des deux nombres lus jusque-là est le plus grand : une lettre $(0 1)$ fait passer en $q_{1}$ , une lettre $(1 0)$ en $q_{0}$ , une lettre à lignes égales ne change rien ; c'est la dernière lettre où les lignes diffèrent, donc le bit de poids fort qui les distingue, qui décide. Vérifié sur les $21845$ mots de longueur $⩽ 7$ .)

Q8. Deux mots de même longueur ont même valeur si et seulement s'ils sont égaux (Q3) : $v_{1} (m) = v_{3} (m)$ équivaut à « chaque lettre a ses lignes 1 et 3 égales ». On devine au départ laquelle des deux égalités on vérifie. Notons $X_{13} = {a \in Σ_{3} ∣ a_{1} = a_{3}}$ et $X_{23} = {a \in Σ_{3} ∣ a_{2} = a_{3}}$ :

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →