Corrigé Mines-Ponts 2026 Informatique I MPI — Partie 3 (Q14 à Q16) : Automate additionneur, multiplication non reconnaissable

Les lettres de ${\Sigma }_3$ sont notées $\left(\begin{array}{c}a\\ b\\ s\end{array}\right)$ ; pour un mot $u$, on note $|u|$ sa longueur et l'on utilise, pour toute lettre $x$ de lignes $x_1,x_2,x_3$, la relation $v_i(ux)=v_i(u)+2^{|u|}{x}_i$ (la nouvelle lettre porte les bits de poids $2^{|u|}$).

Q14. C'est l'addition posée en base $2$, qui commence par les bits de poids faible, justement lus en premier : l'état mémorise la retenue $c\in \{0,1\}$. Depuis la retenue $c$, la lettre $\left(\begin{array}{c}a\\ b\\ s\end{array}\right)$ n'est lisible que si $a+b+c\equiv s[2]$, et elle mène à la retenue $c^{\prime }=\lfloor (a+b+c)/2\rfloor$. L'état initial $r_0$ (retenue nulle) est le seul état final : il ne doit pas rester de retenue à la fin.

L'automate est déterministe (non complet : les quatre lettres restantes bloquent chaque état). En OCaml, avec le type de la partie 2 (l'état $c$ est la retenue) :

let automate_plus = {
  k = 2; n = 3; finaux = [| true; false |];
  delta = (fun c l ->
    let s = l.(0) + l.(1) + c in
    if s mod 2 = l.(2) then [ s / 2 ] else []) }

Exécuté sur les $37449$ mots de longueur $⩽5$ sur ${\Sigma }_3$ : il accepte exactement ceux qui vérifient $v_1+v_2=v_3$. Il passe aussi la déterminisation et la complémentation de la partie 2.