Informatique 1
Mines-PontsMPI2026
Cherchez d'abord seul. En cas de blocage, ouvrez une indication, réessayez, puis seulement la solution.
Rédigé par IA, non vérifié
Signaler une erreur# Mines-Ponts MPI — Informatique 1 2026 · Corrigé guidé
*Corrigé rédigé par IA (La Belle Copie), non officiel. Signalez toute erreur.*
## Présentation du sujet
**Format.** L'épreuve dure 3 heures, sans calculatrice ni dispositif électronique. Le code s'écrit **en OCaml exclusivement** ; les fonctions des modules `List` et `Array` sont permises sans explication, et l'énoncé recommande de s'en tenir aux plus courantes. Le barème tient compte de la clarté et de la concision des programmes. Une annexe fixe les règles de déduction naturelle ; l'énoncé y ajoute deux règles d'égalité, $\mathrm{ax}_=$ ($\Gamma\vdash t=t$) et $\mathrm{sub}_=$ (de $\Gamma,x=t\vdash\varphi[t/x]$ on déduit $\Gamma,x=t\vdash\varphi$), et autorise l'associativité de l'addition dans les arbres. On peut réutiliser le résultat d'une question antérieure sans l'avoir établi.
**Thème.** Le problème démontre que **l'arithmétique de Presburger** (les entiers naturels avec l'addition, sans la multiplication) est **décidable**, en traduisant les formules en automates. L'idée centrale : un $n$-uplet d'entiers est codé par un mot sur l'alphabet $\Sigma_n$ des colonnes de $n$ bits, une lettre par rang binaire, **poids faible en tête**. Un ensemble de $n$-uplets devient un langage, une formule devient un automate, et la vérité d'une formule close se lit sur l'état initial.
**Découpage.**
- **Section 1** (Q1 à Q3) : exponentiation rapide et codage d'une lettre par un entier. Mise en route.
- **Section 2** (Q4 à Q13) : deux automates sur $\Sigma_2$ à analyser (une preuve rigoureuse en Q4), un automate à construire, puis la boîte à outils : test de déterminisme complet, déterminisation (formelle puis en OCaml), complémentaire, produit. Le point délicat est la numérotation des états en Q11.
- **Section 3** (Q14 à Q16) : l'addition est reconnaissable (automate à retenue, avec preuve), la multiplication ne l'est pas.
- **Section 4** (Q17 à Q22) : écrire des formules sans constantes, les mettre sous forme simple, trois preuves en déduction naturelle.
- **Section 5** (Q23 à Q30) : réduction depuis Sat-Cnf, projection d'une ligne, puis l'algorithme formule → automate, son déroulé à la main, son code, sa preuve de correction et son application aux formules closes.
**Notions du programme mobilisées.** Automates finis non déterministes, déterminisation par sous-ensembles, clôture par complémentaire et intersection, lemme de l'étoile, invariants et inductions structurelles, déduction naturelle (y compris quantificateurs), réductions polynomiales et NP-difficulté, OCaml sur tableaux, listes, enregistrements et types sommes.
**Notations de ce corrigé.** Une lettre de $\Sigma_2$ est notée $\binom ab$ et une lettre de $\Sigma_3$ est notée $\langle a,b,c\rangle$ (lignes 1, 2, 3). $\mathbf{0}$ est la lettre nulle. La ligne $i$ de l'énoncé est l'indice `i-1` du tableau OCaml. $\widehat\delta(q,m)$ est l'ensemble des états atteints depuis $q$ en lisant $m$.
**Difficulté et gestion du temps.** Trente questions en trois heures, soit six minutes en moyenne. Le sujet est progressif et très linéaire, mais presque tous les résultats peuvent être admis pour avancer.
- **À ne pas laisser passer** : Q1, Q2, Q3, Q5, Q6, Q7, Q9, Q10, Q13, Q14, Q17, Q20, Q24, Q25, Q30.
- **Le cœur du sujet** : Q4, Q8, Q11, Q12, Q15, Q21, Q22, Q26, Q28.
- **Les plus exigeantes** : Q16 (non-reconnaissabilité), Q18 et Q19 (formules sans constantes, aplatissement des termes), Q23 (réduction), Q27 (déroulé long) et Q29 (preuve de correction).
Lire la section 5 dès le début aide à comprendre où va le sujet, en particulier le rôle de `sans_zero`.
## Partie 1 — Implémentation de quelques fonctions utiles
On fixe le codage d'une lettre de $\Sigma_n$ par un entier et on l'implémente. Outils : exponentiation rapide, division euclidienne, unicité de l'écriture binaire.
### Question 1
> [!INDICATION]
> Exprimez $2^n$ à partir de $2^{\lfloor n/2\rfloor}$, en distinguant selon la parité de $n$.
> [!INDICATION]
> Combien de fois l'appel récursif doit-il être évalué dans un même appel pour que la complexité soit logarithmique ?
#### Solution
```ocaml
(* pow2 n = 2^n, exponentiation rapide *)
let rec pow2 n =
if n = 0 then 1
else
let p = pow2 (n / 2) in
if n mod 2 = 0 then p * p else 2 * p * p
```
**Correction**, par récurrence forte. Pour $n=0$ on renvoie $1=2^0$. Pour $n\ge1$, l'appel sur $\lfloor n/2\rfloor<n$ renvoie $p=2^{\lfloor n/2\rfloor}$ ; on renvoie $p^2=2^n$ si $n$ est pair, $2p^2=2^{2\lfloor n/2\rfloor+1}=2^n$ sinon.
**Complexité.** $C(n)=C(\lfloor n/2\rfloor)+O(1)$, et la suite $n,\lfloor n/2\rfloor,\dots$ atteint $0$ en $\lfloor\log_2 n\rfloor+1$ étapes : $C(n)=O(\log n)$.
> [!PIEGE]
> Écrire `pow2 (n/2) * pow2 (n/2)` recalcule deux fois le même appel : $C(n)=2C(n/2)+O(1)$ donne un coût linéaire, et la complexité demandée est perdue. Il faut nommer le résultat par un `let`.
### Question 2
> [!INDICATION]
> Le sujet lit déjà les mots poids faible en tête : faites de même pour une colonne, lue de haut en bas.
> [!INDICATION]
> Il est plus simple de définir l'application de $\Sigma_n$ vers les entiers, de prouver qu'elle est injective et de conclure par un argument de cardinal.
#### Solution
Soit $\psi(a_1,\dots,a_n)=\sum_{i=1}^n2^{i-1}a_i$.
- $0\le\psi(a)\le\sum_{i=1}^n2^{i-1}=2^n-1$.
- Injectivité : si $a\ne b$, soit $i_0$ le plus grand indice où ils diffèrent, avec $a_{i_0}=1$, $b_{i_0}=0$. Alors $\psi(a)-\psi(b)\ge2^{i_0-1}-\sum_{i<i_0}2^{i-1}=1>0$.
- $|\Sigma_n|=2^n=\big|[\![0,2^n-1]\!]\big|$, donc $\psi$ est bijective.
**La bijection demandée est $\varphi=\psi^{-1}$ : à $x$ on associe la colonne de ses $n$ bits, le bit de poids $2^{i-1}$ en ligne $i$.** Le même argument montre qu'à longueur fixée, un mot de $\{0,1\}^\ell$ est déterminé par sa valeur $v$ : ce fait resservira en Q4 et Q7.
> [!JURY]
> « Exhiber une bijection » demande de prouver qu'elle en est une. Une copie qui se contente de décrire l'application sans justifier la bijectivité laisse la question à moitié traitée.
### Question 3
> [!INDICATION]
> Divisions euclidiennes successives par 2 : le reste donne un bit, le quotient devient la nouvelle valeur.
> [!INDICATION]
> Dans quelle case du tableau doit aller le bit de poids $2^i$ pour respecter la convention de Q2 ?
#### Solution
```ocaml
let decompose x n =
assert (0 <= x && x < pow2 n);
let a = Array.make n 0 in
let r = ref x in
for i = 0 to n - 1 do (* indice i = ligne i+1 *)
a.(i) <- !r mod 2; (* bit de poids 2^i *)
r := !r / 2
done;
a
```
Invariant avant l'itération $i$ : $x=\sum_{j<i}2^j\,\texttt{a.(j)}+2^i\,\texttt{!r}$, conservé par la division euclidienne. En sortie, $x=\psi(\texttt{a})+2^n\,\texttt{!r}$ avec $x<2^n$, donc $\texttt{!r}=0$ : on renvoie $\varphi(x)$. Coût $O(n)$. Exemple : `decompose 6 3` renvoie `[|0;1;1|]`.
> [!PIEGE]
> Remplir le tableau à l'envers (`a.(n-1-i)`) met le poids faible en dernière ligne : tout le reste du sujet devient incohérent. Et l'assertion est explicitement demandée.
## Partie 2 — Automates finis sur $\Sigma_n$
On apprend d'abord à lire des automates sur $\Sigma_2$ comme des relations entre deux entiers (Q4 à Q7), puis on programme la boîte à outils des langages reconnaissables : déterminisation, complémentaire, intersection.
Lecture des figures. $\mathcal{A}_1$ : $q_0$ initial boucle sur $\binom00$, va en $q_1$ par $\binom11$ et en $q_2$ par $\binom10,\binom01$ ; $q_1$ final boucle sur $\binom00,\binom10$ et va en $q_2$ par $\binom01,\binom11$ ; rien ne sort de $q_2$. $\mathcal{A}_2$ : $q_0$ initial boucle sur $\binom00,\binom01,\binom11$ et va en $q_1$ par $\binom10$ ; $q_1$ final boucle sur $\binom00,\binom10,\binom11$ et revient en $q_0$ par $\binom01$.
### Question 4
> [!INDICATION]
> Séparez le travail en deux : décrivez d'abord $\mathcal{L}(\mathcal{A}_1)$ comme un langage explicite (une expression rationnelle), puis comparez ce langage à $E$.
> [!INDICATION]
> Quel est le rôle de $q_2$ ? Un calcul acceptant peut-il y passer ?
> [!INDICATION]
> Côté arithmétique : que vaut $v_2$ si la ligne 2 contient un seul 1 ? Et que dit l'unicité de l'écriture binaire à longueur fixée ? N'oubliez pas le cas $v_1(m)=0$.
#### Solution
Posons $R=\big\{\binom00^k\binom11w\;:\;k\in\mathbb{N},\ w\in\{\binom00,\binom10\}^*\big\}$.
**Étape 1 : $\mathcal{L}(\mathcal{A}_1)=R$.**
- $R\subseteq\mathcal{L}(\mathcal{A}_1)$ : le calcul $q_0\xrightarrow{\binom00^k}q_0\xrightarrow{\binom11}q_1\xrightarrow{w}q_1$ existe et finit en $q_1\in F$.
- $\mathcal{L}(\mathcal{A}_1)\subseteq R$ : un calcul acceptant $q_{(0)}=q_0,\dots,q_{(\ell)}=q_1$ ne passe jamais par $q_2$ (aucune transition n'en sort et $q_2\notin F$). Soit $k$ le premier instant avec $q_{(k+1)}=q_1$. Avant, les transitions $q_0\to q_0$ imposent $\binom00$ ; à l'instant $k$, $q_0\to q_1$ impose $\binom11$ ; ensuite $q_1\to q_1$ impose $\binom00$ ou $\binom10$.
**Étape 2 : $R=E$.** Il n'existe pas de plus grande puissance de 2 divisant $0$ : un mot avec $v_1(m)=0$ n'est pas dans $E$.
- $R\subseteq E$ : pour $m=\binom00^k\binom11w$ et $u=\pi_1(w)$, on a $\pi_1(m)=0^k1u$ et $\pi_2(m)=0^k10^{|w|}$, donc $v_2(m)=2^k$ et $v_1(m)=2^k(1+2v(u))$ avec $1+2v(u)$ impair : la plus grande puissance de 2 qui divise $v_1(m)$ est $2^k=v_2(m)$.
- $E\subseteq R$ : soit $m\in E$, de longueur $\ell$. Alors $v_1(m)\ne0$ ; soit $2^k$ la plus grande puissance de 2 qui le divise. Les bits de $v_1(m)$ de poids inférieur à $2^k$ sont nuls et celui de poids $2^k$ vaut 1 : $\pi_1(m)=0^k1u$, $k\le\ell-1$. Comme $v_2(m)=2^k$, l'unicité de l'écriture binaire sur $\ell$ bits donne $\pi_2(m)=0^k10^{\ell-k-1}$. Donc $m\in R$.
$$\boxed{\mathcal{L}(\mathcal{A}_1)=E}$$
> [!METHODE]
> Pour identifier le langage d'un automate donné : (1) l'écrire comme une expression rationnelle en suivant les calculs possibles, (2) traduire cette forme en propriété arithmétique, (3) conclure par double inclusion. Séparer combinatoire des mots et arithmétique allège chaque étape.
> [!PIEGE]
> Le cas $v_1(m)=0$ (mot vide ou mot de colonnes nulles) : $0$ est divisible par toutes les puissances de 2, il n'en a pas de plus grande. Ces mots ne sont pas dans $E$, et l'automate les rejette bien puisque $q_0$ n'est pas final.
### Question 5
> [!INDICATION]
> Reprenez l'écriture de $v_1(m)$ obtenue en Q4 et isolez $v_2(m)$.
#### Solution
D'après Q4, $v_2(m)=2^k$ et $v_1(m)=2^k+2^{k+1}v(u)$, donc $v_1(m)-v_2(m)=\big(2\times v_2(m)\big)\,v(u)$ avec $v(u)\in\mathbb{N}$ :
$$\boxed{v_1(m)\equiv v_2(m)\ [2\times v_2(m)]}$$
### Question 6
> [!INDICATION]
> Quelles lettres changent l'état, et lesquelles le laissent inchangé ? Que « retient » donc l'état courant ?
> [!INDICATION]
> En lisant poids faible en tête, la dernière position où deux lignes diffèrent est celle du bit de poids le plus fort où les deux entiers diffèrent.
#### Solution
$$\boxed{m\in\mathcal{L}(\mathcal{A}_2)\iff v_1(m)>v_2(m)}$$
(Justification non demandée : par récurrence, après $t$ lettres l'état est $q_1$ si et seulement si la valeur du préfixe de la ligne 1 dépasse strictement celle de la ligne 2, car $(A-B)+2^t(a-b)$ a le signe de $a-b$ si $a\ne b$, puisque $|A-B|<2^t$.)
> [!PIEGE]
> Inégalité large ou stricte ? Testez : $\varepsilon$ n'est pas accepté et $v_1=v_2=0$, donc l'égalité doit donner « faux ». Puis $\binom10$ est accepté ($1>0$) et $\binom10\binom01$ ne l'est pas ($1<2$).
### Question 7
> [!INDICATION]
> Deux lignes d'un même mot ont la même longueur : quand ont-elles la même valeur ?
> [!INDICATION]
> Pour une disjonction avec peu d'états, le non-déterminisme permet de « choisir » à la première lettre quelle condition surveiller. Pensez au mot vide.
#### Solution
À longueur égale, $v_i(m)=v_j(m)\iff\pi_i(m)=\pi_j(m)$ (Q2). On prend trois états $r_0$ (initial), $r_1$, $r_2$, **tous finaux**, et pour $a=\langle a_1,a_2,a_3\rangle$ :
| depuis | vers $r_1$ si | vers $r_2$ si |
|---|---|---|
| $r_0$ | $a_1=a_3$ | $a_2=a_3$ |
| $r_1$ | $a_1=a_3$ | jamais |
| $r_2$ | jamais | $a_2=a_3$ |
$r_0$ accepte $\varepsilon$, qui est dans $L$ ($v_1=v_2=v_3=0$) ; un mot non vide est accepté si toutes ses lettres vérifient $a_1=a_3$ ou toutes vérifient $a_2=a_3$.
> [!PIEGE]
> Oublier de rendre l'état initial final : on rate le mot vide. Une variante déterministe incomplète à trois états existe aussi (« les deux égalités tiennent encore », « seule la première », « seule la seconde »).
### Question 8
> [!INDICATION]
> Pour parcourir toutes les lettres de $\Sigma_n$, utilisez la bijection de Q2 et la fonction de Q3.
> [!INDICATION]
> Comment tester qu'une liste a exactement un élément sans la parcourir en entier ?
#### Solution
```ocaml
let est_deterministe_complet a =
let ok = ref true in
for x = 0 to pow2 a.n - 1 do (* x parcourt les 2^n lettres *)
let lettre = decompose x a.n in
for q = 0 to a.k - 1 do
match a.delta q lettre with
| [_] -> () (* exactement un successeur *)
| _ -> ok := false
done
done;
!ok
```
**Correction.** La double boucle examine chaque couple $(q,a)\in Q\times\Sigma_n$ une fois ; `ok` reste vrai si et seulement si chaque $\delta(q,a)$ (liste sans doublon) a un seul élément.
**Complexité.** Un appel à `delta` reçoit une lettre de taille $n$ : on le compte $O(n)$. Le filtrage `[_]` est en $O(1)$. Pour chacune des $2^n=|\Sigma_n|$ lettres, `decompose` coûte $O(n)$ et les $|Q|$ appels $O(n|Q|)$ ; `pow2 a.n` est calculé une fois en $O(\log n)$. Total : $O(n\times|Q|\times|\Sigma_n|)$.
> [!PIEGE]
> `List.length (a.delta q lettre) = 1` parcourt toute la liste, qui peut contenir jusqu'à $|Q|$ états : la borne demandée n'est plus garantie. Le filtrage sur `[_]` évite ce surcoût.
> [!JURY]
> La complexité est explicitement à justifier : il faut dire combien de lettres on énumère, ce que coûte chaque étape, et sous quelle hypothèse de coût pour un appel à `delta`.
### Question 9
> [!INDICATION]
> Un état du nouvel automate représente l'ensemble des états où l'automate de départ « pourrait se trouver ».
> [!INDICATION]
> Précisez l'état initial, la transition (une union) et les états finaux, puis justifiez par une récurrence sur la longueur du mot.
#### Solution
$$\mathcal{A}^d=\big(\Sigma,\ \mathcal{P}(Q),\ \{q_0\},\ F^d,\ \delta^d\big),\qquad\delta^d(S,a)=\Big\{\bigcup_{q\in S}\delta(q,a)\Big\},\qquad F^d=\{S\subseteq Q\mid S\cap F\ne\emptyset\}.$$
Chaque $\delta^d(S,a)$ est un singleton : $\mathcal{A}^d$ est déterministe complet, $\emptyset$ jouant le rôle de puits. Par récurrence sur $|m|$, l'état atteint depuis $S$ en lisant $m$ est $\bigcup_{q\in S}\widehat\delta(q,m)$. Donc $m\in\mathcal{L}(\mathcal{A}^d)\iff\widehat\delta(q_0,m)\cap F\ne\emptyset\iff m\in\mathcal{L}(\mathcal{A})$.
> [!METHODE]
> La construction par sous-ensembles se retient avec son invariant : « l'état du déterminisé est l'ensemble des états accessibles ». C'est lui qui donne la preuve en deux lignes.
### Question 10
> [!INDICATION]
> Partez d'un tableau neuf rempli de 0, puis marquez les successeurs de chaque état présent dans `etats`.
#### Solution
```ocaml
let union etats a lettre =
let t = Array.make a.k 0 in
for q = 0 to a.k - 1 do
if etats.(q) = 1 then
List.iter (fun i -> t.(i) <- 1) (a.delta q lettre)
done;
t
```
`t.(i)` vaut 1 exactement s'il existe $q$ avec `etats.(q) = 1` et $q\xrightarrow{\texttt{lettre}}i$. Le tableau `etats` n'est pas modifié.
> [!PIEGE]
> Le résultat doit partir de zéros. Partir d'une copie de `etats` (ou modifier `etats` en place) ajouterait à tort les états de départ.
### Question 11
> [!INDICATION]
> Une partie de $[\![0,k-1]\!]$ se représente par un vecteur de $\{0,1\}^k$, c'est-à-dire une lettre de $\Sigma_k$, donc par un entier : d'où l'indication d'utiliser `decompose`.
> [!INDICATION]
> L'énoncé impose que l'état initial porte le numéro 0. Quel entier code la partie $\{q_0\}$ ? Comment renuméroter sans perdre la bijection ?
> [!INDICATION]
> Il faut aussi la fonction réciproque, du vecteur caractéristique vers le numéro d'état.
#### Solution
Le singleton $\{0\}$ a pour code $1$ ; on numérote les états par la transposition qui échange les codes $0$ et $1$.
```ocaml
(* involution de [0, 2^k - 1] : échange 0 et 1 *)
let echange x = if x = 0 then 1 else if x = 1 then 0 else x
let determinise a =
let kd = pow2 a.k in
let ens i = decompose (echange i) a.k in (* numéro -> partie *)
let code t = (* partie -> numéro *)
let x = ref 0 and p = ref 1 in
for q = 0 to a.k - 1 do
if t.(q) = 1 then x := !x + !p;
p := 2 * !p
done;
echange !x
in
let finaux = Array.make kd false in
for i = 0 to kd - 1 do
let s = ens i in
for q = 0 to a.k - 1 do
if s.(q) = 1 && a.finaux.(q) then finaux.(i) <- true
done
done;
{ k = kd; n = a.n; finaux = finaux;
delta = (fun i lettre -> [ code (union (ens i) a lettre) ]) }
```
**Correction.** `ens` est une bijection des numéros sur les parties et `code` est sa réciproque ; l'état $0$ code $\{q_0\}$. `delta` renvoie toujours un singleton (déterministe complet), celui du code de $\bigcup_{q\in S}\delta(q,a)$, et `finaux.(i)` est vrai si et seulement si la partie rencontre $F$ : c'est l'automate de Q9.
> [!PIEGE]
> Numéroter les parties par leur code brut met $\emptyset$ en position 0, qui deviendrait l'état initial : l'automate ne reconnaîtrait plus rien. Le ou exclusif avec 1 (`x lxor 1`) est une autre involution qui convient.
> [!PIEGE]
> L'ensemble vide doit rester un état (le puits) : `delta` renvoie une liste à un élément même quand aucun successeur n'existe dans l'automate de départ.
### Question 12
> [!INDICATION]
> Échanger finaux et non-finaux ne donne le complémentaire que sous une hypothèse précise sur l'automate.
> [!INDICATION]
> Vous disposez d'un test (Q8) et d'une construction (Q11).
#### Solution
```ocaml
let complementaire a =
let d = if est_deterministe_complet a then a else determinise a in
{ k = d.k; n = d.n; finaux = Array.map not d.finaux; delta = d.delta }
```
$d$ est déterministe complet et reconnaît $\mathcal{L}(a)$. Tout mot $m$ a un unique calcul dans $d$ ; il est accepté par le résultat si et seulement si ce calcul finit hors de $F_d$, c'est-à-dire si $m\notin\mathcal{L}(a)$.
> [!PIEGE]
> Sans complétude, un mot qui n'a aucun calcul est rejeté avant et après l'échange. Exemple : l'automate à un état final bouclant sur $\binom00$ et $\binom11$ ; échanger les finaux donne le langage vide, pas le complémentaire.
> [!METHODE]
> `Array.map` renvoie un tableau neuf : on ne modifie jamais les champs de l'automate reçu, qui peut être partagé ailleurs.
### Question 13
> [!INDICATION]
> Faites fonctionner les deux automates en parallèle sur le même mot.
> [!INDICATION]
> Pour la preuve, montrez par récurrence que l'ensemble des couples atteints est un produit d'ensembles.
#### Solution
$$\mathcal{A}_\cap=\big(\Sigma_n,\ Q_1\times Q_2,\ (q_1,q_2),\ F_1\times F_2,\ \delta\big),\qquad\delta\big((p,q),a\big)=\delta_1(p,a)\times\delta_2(q,a).$$
Par récurrence sur $|m|$, $\widehat\delta\big((q_1,q_2),m\big)=\widehat\delta_1(q_1,m)\times\widehat\delta_2(q_2,m)$, car une union de produits $\delta_1(p',a)\times\delta_2(q',a)$ indexée par un produit est le produit des unions. Et $(R_1\times R_2)\cap(F_1\times F_2)\ne\emptyset$ si et seulement si $R_1\cap F_1\ne\emptyset$ et $R_2\cap F_2\ne\emptyset$. Donc $\mathcal{L}(\mathcal{A}_\cap)=\mathcal{L}(\mathcal{A}_1)\cap\mathcal{L}(\mathcal{A}_2)$, sans hypothèse de déterminisme.
> [!PIEGE]
> Pour l'intersection, les finaux sont $F_1\times F_2$ ; $(F_1\times Q_2)\cup(Q_1\times F_2)$ donnerait l'union, et seulement pour des automates complets.
## Partie 3 — Opérations arithmétiques
On montre que l'addition se calcule par un automate fini (la retenue est une mémoire bornée) et que la multiplication ne le peut pas (lemme de l'étoile).
### Question 14
> [!INDICATION]
> Posez l'addition à la main, colonne par colonne en commençant par le poids faible : quelle information faut-il mémoriser d'une colonne à la suivante ?
> [!INDICATION]
> Écrivez la condition sur la lettre $\langle\alpha,\beta,\sigma\rangle$, la retenue entrante $c$ et la retenue sortante $c'$. Quel état doit être final ?
#### Solution
Deux états : $r_0$ (retenue 0, initial et **seul final**) et $r_1$ (retenue 1). La transition $r_c\xrightarrow{\langle\alpha,\beta,\sigma\rangle}r_{c'}$ existe si et seulement si $\alpha+\beta+c=\sigma+2c'$ :
| depuis | lettre $\to r_0$ | lettre $\to r_1$ |
|---|---|---|
| $r_0$ | $\langle0,0,0\rangle,\ \langle1,0,1\rangle,\ \langle0,1,1\rangle$ | $\langle1,1,0\rangle$ |
| $r_1$ | $\langle0,0,1\rangle$ | $\langle1,0,0\rangle,\ \langle0,1,0\rangle,\ \langle1,1,1\rangle$ |
Les autres couples (état, lettre) n'ont pas de transition : le mot est rejeté.
> [!PIEGE]
> Rendre $r_1$ final : $\langle1,1,0\rangle$ mène en $r_1$ alors que $1+1\ne0$. Une retenue finale non nulle signifie que la somme ne tient pas sur la longueur du mot.
### Question 15
> [!INDICATION]
> Formulez un invariant reliant les valeurs des préfixes de longueur $t$ des trois lignes et l'état atteint. La retenue sortante pèse $2^t$.
> [!INDICATION]
> L'invariant doit être une équivalence : « un calcul existe si et seulement si… ». Le sens réciproque garantit qu'aucun mot de $L_+$ n'est rejeté faute de transition.
> [!INDICATION]
> Pour le sens réciproque, encadrez $A_t+B_t-S_t$ pour montrer que la retenue reconstituée vaut 0 ou 1.
#### Solution
Pour $m=m_0\cdots m_{\ell-1}$ avec $m_t=\langle\alpha_t,\beta_t,\sigma_t\rangle$, posons $A_t=\sum_{j<t}2^j\alpha_j$, et $B_t$, $S_t$ de même : ces valeurs sont dans $[\![0,2^t-1]\!]$ et $A_\ell=v_1(m)$, $B_\ell=v_2(m)$, $S_\ell=v_3(m)$.
**$\mathcal{P}(t)$** : un calcul depuis $r_0$ sur $m_0\cdots m_{t-1}$ existe si et seulement s'il existe $c\in\{0,1\}$ avec $A_t+B_t=S_t+2^tc$ ; ce $c$ est unique et le calcul (unique) arrive en $r_c$.
$\mathcal{P}(0)$ est clair ($c=0$). Supposons $\mathcal{P}(t)$ et notons $m_t=\langle\alpha,\beta,\sigma\rangle$.
- ($\Rightarrow$) Le calcul passe par $r_c$ avec $A_t+B_t=S_t+2^tc$, puis emprunte $r_c\xrightarrow{m_t}r_{c'}$, donc $\alpha+\beta+c=\sigma+2c'$ ; d'où $A_{t+1}+B_{t+1}=S_t+2^t(c+\alpha+\beta)=S_{t+1}+2^{t+1}c'$.
- ($\Leftarrow$) Si $A_{t+1}+B_{t+1}=S_{t+1}+2^{t+1}c'$ avec $c'\in\{0,1\}$, alors $A_t+B_t=S_t+2^tc$ où $c=\sigma-\alpha-\beta+2c'$. De $-(2^t-1)\le A_t+B_t-S_t\le2(2^t-1)$ on tire $-2^t<2^tc<2^{t+1}$, donc $c\in\{0,1\}$. Par $\mathcal{P}(t)$ le calcul arrive en $r_c$, et $\alpha+\beta+c=\sigma+2c'$ est la condition d'existence de $r_c\xrightarrow{m_t}r_{c'}$.
- L'unicité de $c'$ vient de $2^{t+1}c'=A_{t+1}+B_{t+1}-S_{t+1}$.
Pour $t=\ell$ : $m$ est accepté si et seulement si le calcul existe et arrive en $r_0$, c'est-à-dire $v_1(m)+v_2(m)=v_3(m)$. **L'automate reconnaît $L_+$.**
> [!METHODE]
> Prouver qu'un automate reconnaît un langage, c'est presque toujours exhiber ce que « signifie » chaque état et le démontrer par récurrence sur la longueur du préfixe lu. L'invariant à prouver est celui qui a servi à construire l'automate.
> [!PIEGE]
> Ne prouver que le sens direct : on obtient $\mathcal{L}\subseteq L_+$, mais pas qu'un mot de $L_+$ possède un calcul.
### Question 16
> [!INDICATION]
> L'outil au programme pour prouver qu'un langage n'est pas reconnaissable est le lemme de l'étoile (ou, ce qui revient au même, un argument de tiroirs sur les états).
> [!INDICATION]
> Choisissez un mot de $L_\times$ dont le début ne contient que des colonnes nulles : le facteur pompé sera forcé d'y tomber.
> [!INDICATION]
> Insérer $\lambda$ colonnes nulles en tête multiplie chaque valeur par $2^\lambda$. Comment se comportent alors $v_1v_2$ et $v_3$ ?
#### Solution
**Non, $L_\times$ n'est pas reconnaissable.** Supposons-le reconnu par un automate à $N$ états, et soit $p=N$. Le mot $m$ de longueur $2p+1$ tel que
$$\pi_1(m)=0^p\,1\,0^p,\qquad\pi_2(m)=0^p\,1\,0^p,\qquad\pi_3(m)=0^{2p}\,1$$
vérifie $v_1(m)=v_2(m)=2^p$ et $v_3(m)=2^{2p}$ : $m\in L_\times$. Le lemme de l'étoile donne $m=xyz$ avec $|xy|\le p$, $y\ne\varepsilon$ et $xy^iz\in L_\times$ pour tout $i$. Les $p$ premières lettres valent $\mathbf{0}$, donc $y=\mathbf{0}^\lambda$, $\lambda\ge1$. Alors $v_1(xy^2z)=v_2(xy^2z)=2^{p+\lambda}$ et $v_3(xy^2z)=2^{2p+\lambda}\ne2^{2p+2\lambda}$ : $xy^2z\notin L_\times$, contradiction.
> [!PIEGE]
> Un argument du type « il y a une infinité de produits » ne prouve rien : $L_+$ est tout aussi infini et il est reconnaissable. Seule la structure du pompage fait la différence.
> [!METHODE]
> Quand on veut contrôler le facteur pompé, on place un préfixe « neutre » de longueur au moins le nombre d'états : la contrainte $|xy|\le N$ force $y$ à y tomber, quelle que soit la factorisation.
## Partie 4 — Arithmétique de Presburger
On apprend à écrire des propriétés sans constantes ni multiplication, on normalise les formules (forme simple, utilisée en section 5), puis on rédige des preuves formelles avec les règles de l'annexe et les deux règles d'égalité.
### Question 17
> [!INDICATION]
> Être pair, c'est être le double d'un entier ; comment écrire un double sans multiplication ?
#### Solution
$$\boxed{\mathrm{div}_2(x):=\exists y.\ x=y+y}$$
Sous l'assignation $x\mapsto k$, elle est vraie si et seulement s'il existe $j\in\mathbb{N}$ avec $k=2j$.
### Question 18
> [!INDICATION]
> Aucune constante n'est un terme, ni $n$, ni $1$, ni $0$. Commencez par trouver une formule à une variable libre vraie seulement pour $0$.
> [!INDICATION]
> Caractérisez ensuite $1$ parmi les entiers non nuls par une propriété additive. Enfin, $n$ est une somme de $n$ copies de $1$.
#### Solution
- $\mathrm{zero}(z):=(z=z+z)$ : dans $\mathbb{N}$, $z=2z$ si et seulement si $z=0$.
- $\mathrm{un}(u):=\neg(u=u+u)\wedge\neg\exists s.\exists t.\big(\neg(s=s+s)\wedge\neg(t=t+t)\wedge u=s+t\big)$ : $u$ est non nul et n'est pas somme de deux non-nuls. Si $u=1$, toute écriture $1=s+t$ a un terme nul ; si $u\ge2$, $u=1+(u-1)$ convient ; $u=0$ est exclu par le premier conjoint. Donc $\mathrm{un}(u)\iff u=1$.
$$\boxed{f_0(x):=\big(x=x+x\big),\qquad f_n(x):=\exists u.\Big(\mathrm{un}(u)\wedge x=\underbrace{u+\cdots+u}_{n\text{ termes}}\Big)\quad(n\ge1)}$$
Pour $n\ge1$ la formule est vraie si et seulement s'il existe $u=1$ avec $a(x)=nu$, soit $a(x)=n$. Les variables $u,s,t$ sont liées et distinctes de $x$.
> [!PIEGE]
> Écrire $x=1+1+\cdots+1$ : $1$ n'est pas plus un terme que $n$. Il faut définir $1$ par une formule, et traiter $n=0$ à part (une somme vide n'est pas un terme).
### Question 19
> [!INDICATION]
> Trois défauts à corriger : les connecteurs $\vee$ et $\to$, le quantificateur $\forall$, et les atomes dont les membres sont des sommes de plus de deux variables (ou dont le membre gauche n'est pas une variable).
> [!INDICATION]
> Pour les connecteurs, pensez aux lois de De Morgan et à la dualité entre $\forall$ et $\exists$.
> [!INDICATION]
> Pour les atomes, nommez chaque somme partielle par une variable fraîche quantifiée existentiellement : pourquoi cela ne change-t-il pas la valeur de vérité ?
#### Solution
On construit par induction structurelle une formule $S(\varphi)$ sous forme simple, équivalente à $\varphi$ et de mêmes variables libres ; les variables introduites sont fraîches ($\mathcal{V}$ est infini).
**Atomes.** Tout terme s'écrit $y_1+\cdots+y_p$ avec des variables $y_r$ (induction et associativité). *Lemme* : si $z$ n'apparaît ni dans $t$ ni dans $\psi$, $\exists z.(z=t\wedge\psi)$ équivaut à $\psi[t/z]$, puisque le seul témoin possible est la valeur de $t$. Pour $y_1+\cdots+y_p=y'_1+\cdots+y'_q$, avec $z_1:=y_1$, $z'_1:=y'_1$ et des variables fraîches $z_2,\dots,z_p,z'_2,\dots,z'_q$ :
$$S(t_1=t_2):=\exists z_2\cdots\exists z_p\,\exists z'_2\cdots\exists z'_q.\Big(\bigwedge_{r=2}^pz_r=z_{r-1}+y_r\ \wedge\ \bigwedge_{s=2}^qz'_s=z'_{s-1}+y'_s\ \wedge\ z_p=z'_q\Big).$$
Chaque atome est de la forme permise par (iii), et le lemme appliqué de l'intérieur vers l'extérieur redonne l'atome initial.
**Connecteurs.**
$$\begin{aligned}S(\neg\varphi)&:=\neg S(\varphi), & S(\varphi_1\wedge\varphi_2)&:=S(\varphi_1)\wedge S(\varphi_2), & S(\exists x.\varphi)&:=\exists x.S(\varphi),\\ S(\varphi_1\vee\varphi_2)&:=\neg\big(\neg S(\varphi_1)\wedge\neg S(\varphi_2)\big), & S(\varphi_1\to\varphi_2)&:=\neg\big(S(\varphi_1)\wedge\neg S(\varphi_2)\big), & S(\forall x.\varphi)&:=\neg\exists x.\neg S(\varphi).\end{aligned}$$
Ces équivalences valent sous toute assignation, et $\neg$, $\wedge$, $\exists$ ne dépendent de leurs sous-formules que par leurs valeurs de vérité : l'hypothèse d'induction se propage, et (i), (ii), (iii) sont stables par ces trois constructeurs. **Toute formule est équivalente à une formule sous forme simple.**
> [!PIEGE]
> Oublier la condition (iii). C'est pourtant elle qui rend la section 5 possible : les seuls automates de base fournis reconnaissent $v_i=v_j$ et $v_i+v_j=v_k$.
> [!PIEGE]
> Réutiliser une variable déjà présente au lieu d'une variable fraîche : on capturerait une variable libre et l'équivalence serait perdue.
### Question 20
> [!INDICATION]
> Lisez l'arbre de bas en haut : commencez par les introductions d'implication pour placer les hypothèses dans le contexte.
> [!INDICATION]
> Éliminez ensuite la disjonction : l'une des deux branches se ferme par un axiome, l'autre par une contradiction.
#### Solution
Avec $A=\varphi(x)$, $B=\psi(y)$ et $\Gamma=\{A\vee B,\neg A\}$ :
$$\dfrac{\dfrac{\dfrac{\Gamma\vdash A\vee B\ (\mathrm{ax})\qquad\dfrac{\dfrac{\Gamma,A\vdash\neg A\ (\mathrm{ax})\qquad\Gamma,A\vdash A\ (\mathrm{ax})}{\Gamma,A\vdash\bot}\,\neg e}{\Gamma,A\vdash B}\,\bot\qquad\Gamma,B\vdash B\ (\mathrm{ax})}{\Gamma\vdash B}\,\vee e}{A\vee B\vdash\neg A\to B}\,\to i}{\vdash(A\vee B)\to(\neg A\to B)}\,\to i$$
Aucune règle de quantificateur n'intervient : les variables $x$ et $y$ ne jouent aucun rôle.
> [!PIEGE]
> La règle $\vee e$ de l'annexe a trois prémisses : il faut écrire les trois. Et le passage de $\bot$ à $B$ se fait par la règle $\bot$ ; le raisonnement par l'absurde n'est pas nécessaire.
### Question 21
> [!INDICATION]
> La formule doit être close : quantifiez toutes les variables.
> [!INDICATION]
> La règle $\mathrm{sub}_=$ se lit de bas en haut : pour prouver $\varphi$ sous l'hypothèse $x=t$, il suffit de prouver $\varphi$ où $x$ est remplacé par $t$. Avec quelle hypothèse et quelle formule l'appliquer ?
> [!INDICATION]
> La règle cut de l'annexe transforme deux hypothèses en une conjonction.
#### Solution
$$\boxed{T:=\forall x.\forall y.\forall z.\Big(\big(x=y\wedge y=z\big)\to x=z\Big)}$$
Avec $\Delta=\{y=z,\ x=y\}$, instance de $\mathrm{sub}_=$ : variable $x$, terme $y$, contexte $\{y=z\}$, formule $x=z$, dont la substitution $(x=z)[y/x]$ est $y=z$.
$$\dfrac{\dfrac{\dfrac{\dfrac{\dfrac{\Delta\vdash y=z\ (\mathrm{ax})}{\Delta\vdash x=z}\,\mathrm{sub}_=}{x=y\wedge y=z\vdash x=z}\,\mathrm{cut}}{\vdash(x=y\wedge y=z)\to x=z}\,\to i}{\vdash\forall z.\big((x=y\wedge y=z)\to x=z\big)}\,\forall i}{\vdash T}\,\forall i\ (\times2)$$
Les $\forall i$ sont licites car le contexte est vide.
> [!JURY]
> Un arbre de preuve n'est vérifiable que si chaque application d'une règle à paramètres est explicitée : quelle variable, quel terme, quelle formule. C'est une exigence générale de rigueur, qui vaut particulièrement pour $\mathrm{sub}_=$.
### Question 22
> [!INDICATION]
> Sémantiquement, la formule dit que l'ordre $\le$ est transitif. Quel est le témoin naturel pour $c$ ? Attention : seule l'associativité est autorisée.
> [!INDICATION]
> Lisez de bas en haut : $\forall i$, $\to i$, puis la règle $\exists e'$ (deux fois) pour faire entrer $a$ et $b$ dans le contexte, puis cut, puis $\exists i$.
> [!INDICATION]
> Pour obtenir l'égalité finale, appliquez deux fois $\mathrm{sub}_=$, en partant d'une instance de $\mathrm{ax}_=$. Écrivez à chaque fois quelle hypothèse sert.
#### Solution
Soit $\Delta=\{x=y+a,\ y=z+b\}$ et $\Phi:=\big(\exists a.\exists b.(x=y+a\wedge y=z+b)\big)\to\exists c.\,x=z+c$. Le témoin est $c:=b+a$.
**Étape 1.**
$$\dfrac{\dfrac{\Delta\vdash z+b+a=z+b+a\ (\mathrm{ax}_=)}{\Delta\vdash y+a=z+b+a}\,\mathrm{sub}_=}{\Delta\vdash x=z+b+a}\,\mathrm{sub}_=$$
- Premier $\mathrm{sub}_=$ : variable $y$, terme $z+b$, contexte $\{x=y+a\}$, formule $y+a=z+b+a$ ; la substitution donne $(z+b)+a=z+b+a$, instance de $\mathrm{ax}_=$ à l'associativité près.
- Second $\mathrm{sub}_=$ : variable $x$, terme $y+a$, contexte $\{y=z+b\}$, formule $x=z+b+a$ ; la substitution donne $y+a=z+b+a$.
**Étape 2.** $(x=z+c)[b+a/c]$ est $x=z+(b+a)$, c'est-à-dire $x=z+b+a$ :
$$\dfrac{\dfrac{\dfrac{\dfrac{\dfrac{\dfrac{\Delta\vdash x=z+b+a}{\Delta\vdash\exists c.\,x=z+c}\,\exists i}{x=y+a\wedge y=z+b\vdash\exists c.\,x=z+c}\,\mathrm{cut}}{\exists b.(x=y+a\wedge y=z+b)\vdash\exists c.\,x=z+c}\,\exists e'}{\exists a.\exists b.(x=y+a\wedge y=z+b)\vdash\exists c.\,x=z+c}\,\exists e'}{\vdash\Phi}\,\to i}{\vdash\forall x.\forall y.\forall z.\,\Phi}\,\forall i\ (\times3)$$
Conditions de bord : pour les deux $\exists e'$, le contexte restant est vide et $FV(\exists c.\,x=z+c)=\{x,z\}$ ne contient ni $b$ ni $a$ ; pour les $\forall i$, le contexte est vide.
> [!PIEGE]
> Prendre $c:=a+b$ impose de passer de $z+b+a$ à $z+a+b$, donc d'utiliser la commutativité, qui n'est pas fournie. Le témoin $b+a$ évite le problème.
> [!PIEGE]
> Appliquer $\mathrm{sub}_=$ « à l'envers » : la règle remplace, en remontant, la variable par le terme. Avec l'hypothèse $y=z+b$, on transforme un but contenant $y$ en un but contenant $z+b$, pas l'inverse.
## Partie 5 — Retour sur les automates
On relie tout : la satisfiabilité propositionnelle se code dans Presburger (difficulté), puis chaque formule sous forme simple se compile en automate (décidabilité). Le point technique est la gestion des zéros non significatifs lors de la quantification existentielle.
### Question 23
> [!INDICATION]
> Il faut transformer, en temps polynomial, une CNF en une formule de Presburger close, vraie exactement quand la CNF est satisfiable. Que doit traduire un quantificateur existentiel ?
> [!INDICATION]
> Codez la valeur de vérité d'une variable propositionnelle par une propriété d'un entier, exprimable sans constante (voir Q18).
#### Solution
Soit $\varphi$ une CNF sur $p_1,\dots,p_N$. On prend des variables distinctes $u_1,\dots,u_N$ et on remplace chaque $p_i$ par $T_i:=\neg(u_i=u_i+u_i)$ (« $u_i\ne0$ »), en gardant $\neg$, $\wedge$, $\vee$ ; on obtient $\mathrm{tr}(\varphi)$ et
$$\boxed{\Psi:=\exists u_1.\exists u_2\cdots\exists u_N.\ \mathrm{tr}(\varphi)}$$
formule close. À $(n_1,\dots,n_N)\in\mathbb{N}^N$ correspond la valuation $\theta(p_i)=(n_i\ne0)$, et toute valuation s'obtient ainsi ; par induction, $\mathrm{tr}(\alpha)$ est vraie sous $(n_i)$ si et seulement si $\alpha$ est vraie sous $\theta$. Donc **$\Psi$ est vraie si et seulement si $\varphi$ est satisfiable**. La taille est $O(|\varphi|)$, la construction linéaire : c'est une réduction polynomiale. Comme Sat-Cnf est NP-complet, Tautologie-Presburger est NP-difficile.
> [!PIEGE]
> Le sens de la réduction : on transforme une instance de Sat-Cnf en instance de Tautologie-Presburger. Et sans les quantificateurs existentiels, la formule obtenue aurait des variables libres : ce ne serait pas une instance du problème cible.
### Question 24
> [!INDICATION]
> Un mot de $L_{\exists2}$ a la même longueur et les mêmes lignes 1 et 3 qu'un mot de $L$ ; seule la ligne 2 est libre.
#### Solution
Avec $L=\{\varepsilon,\ \langle0,1,1\rangle,\ \langle0,0,0\rangle\langle1,1,1\rangle\}$ :
$$\boxed{L_{\exists2}=\big\{\varepsilon,\ \langle0,0,1\rangle,\ \langle0,1,1\rangle,\ \langle0,\beta,0\rangle\langle1,\beta',1\rangle\ \text{pour}\ \beta,\beta'\in\{0,1\}\big\}}$$
soit $1+2+4=7$ mots.
> [!PIEGE]
> L'opération ne change pas la longueur des mots. C'est précisément cette limitation que `sans_zero` corrigera en Q26.
### Question 25
> [!INDICATION]
> Gardez les états, l'état initial et les finaux ; seule la transition change. À la lecture d'une lettre, l'automate doit « deviner » la composante $i$.
> [!INDICATION]
> Attention au décalage d'indice entre lignes mathématiques et tableaux, et à ne pas modifier la lettre reçue.
#### Solution
$\delta'(q,a)=\delta(q,a[i\leftarrow0])\cup\delta(q,a[i\leftarrow1])$, où $a[i\leftarrow\beta]$ est $a$ avec la composante $i$ égale à $\beta$.
```ocaml
let automate_existe a i =
let delta' q lettre =
let l0 = Array.copy lettre and l1 = Array.copy lettre in
l0.(i - 1) <- 0; (* ligne i = indice i-1 *)
l1.(i - 1) <- 1;
List.sort_uniq compare (a.delta q l0 @ a.delta q l1)
in
{ k = a.k; n = a.n; finaux = a.finaux; delta = delta' }
```
**Correction.** Un calcul acceptant de $m$ dans le nouvel automate choisit à chaque pas un bit $\beta_t$ : le mot $w$ de lettres $m_t[i\leftarrow\beta_t]$ est accepté par $\mathcal{A}$ et coïncide avec $m$ hors de la ligne $i$. Réciproquement, si $w\in\mathcal{L}(\mathcal{A})$ coïncide avec $m$ hors de la ligne $i$, alors $|w|=|m|$, $\delta(q,w_t)\subseteq\delta'(q,m_t)$, et le calcul acceptant de $w$ en est un pour $m$.
> [!PIEGE]
> Modifier `lettre` en place : la lettre appartient à l'appelant (par exemple à la boucle de `determinise`), et la muter fausse les calculs suivants. D'où les deux copies.
### Question 26
> [!INDICATION]
> La forme simple n'a que quatre constructeurs (deux sortes d'atomes, $\neg$, $\wedge$, $\exists$) : associez à chacun une opération sur les automates déjà disponible.
> [!INDICATION]
> Pour $\exists$, la projection de Q25 suffit-elle ? Pensez à un témoin plus grand que ce que la longueur du mot permet de coder.
> [!INDICATION]
> Que deviennent les valeurs $v_k$ quand on ajoute des lettres nulles à droite d'un mot ?
#### Solution
On fixe $n$ (plus grand indice de variable) : tous les automates sont sur $\Sigma_n$, la ligne $i$ portant $x_i$. On procède **récursivement sur la formule** :
- **$x_i=x_j$** : `automate_egalite n i j`.
- **$x_i=x_j+x_k$** : `automate_somme n j k i` (qui reconnaît $v_j+v_k=v_i$ ; elle suppose $n\ge3$).
- **$\neg\psi$** : complémentaire (Q12) de l'automate de $\psi$.
- **$\psi_1\wedge\psi_2$** : intersection des deux automates.
- **$\exists x_i.\psi$** : `automate_existe` sur la ligne $i$ appliqué à l'automate de $\psi$, puis `sans_zero`.
**Pourquoi `sans_zero`.** La projection ne change pas la longueur : elle ne propose pour $x_i$ que des valeurs codables sur $|m|$ bits, alors que $\exists x_i$ porte sur tout $\mathbb{N}$. Ajouter des lettres $\mathbf{0}$ à droite ne change aucune valeur $v_k$ (bits de poids fort nuls) : un mot $m$ doit être accepté dès qu'un allongement $m\mathbf{0}^j$ laisse la place au témoin, ce que réalise `sans_zero`. Exemple ($n=3$) : pour $\exists x_1.\,x_1=x_2+x_2$, le mot de longueur 1 avec $v_2=1$ doit être accepté (témoin 2), mais aucun mot de longueur 1 ne code 2 sur la ligne 1.
> [!PIEGE]
> L'ordre des arguments de `automate_somme` : elle reconnaît « ligne $i$ $+$ ligne $j$ $=$ ligne $k$ », alors que l'atome s'écrit $x_i=x_j+x_k$. Il faut donc l'appeler avec $(j,k,i)$.
### Question 27
> [!INDICATION]
> Partez de la feuille ($x_1=x_2$) et remontez : complémentaire, projection de la ligne 1, `sans_zero`, complémentaire. Précisez l'automate que vous supposez renvoyé par `automate_egalite`.
> [!INDICATION]
> À chaque complémentaire, demandez-vous si l'automate est déterministe complet : sinon le code déterminise, et numérote les parties comme en Q11.
> [!INDICATION]
> Vérifiez le résultat par la sémantique : que vaut $\neg\exists x_1.\neg(x_1=x_2)$ pour un $x_2$ donné ?
#### Solution
On suppose que `automate_egalite 2 1 2` renvoie l'automate à un état $s$, initial et final, bouclant sur $\binom00$ et $\binom11$, sans autre transition ($\mathcal{B}_1$, langage $v_1=v_2$).
**Étape 2 — $\neg(x_1=x_2)$.** $\mathcal{B}_1$ n'est pas complet : on déterminise (2 états, état $0=\{s\}$, état $1=\emptyset$) puis on échange les finaux.
| état | $\binom00,\binom11$ | $\binom01,\binom10$ | final après échange |
|---|---|---|---|
| $0=\{s\}$ | $0$ | $1$ | non |
| $1=\emptyset$ | $1$ | $1$ | oui |
$\mathcal{B}_2$ reconnaît $\{m\mid v_1(m)\ne v_2(m)\}$.
**Étape 3 — projection de la ligne 1.** Depuis $0$, une lettre de ligne 2 égale à $b$ donne $\binom0b$ et $\binom1b$, l'une vers $0$, l'autre vers $1$ : $\delta_3(0,a)=\{0,1\}$ ; $\delta_3(1,a)=\{1\}$. Finaux $\{1\}$ : $\mathcal{B}_3$ reconnaît les mots non vides.
**Étape 4 — `sans_zero`.** Depuis $0$, la lettre $\binom00$ mène en $1$, final : $0$ devient final. $\mathcal{B}_4$ a tous ses états finaux et reconnaît $\Sigma_2^*$ ; sans `sans_zero`, le mot vide ($x_2=0$) aurait été rejeté à tort, alors que $x_1=1$ convient.
**Étape 5 — négation extérieure.** $\mathcal{B}_4$ n'est pas déterministe : le code construit les 4 parties de $\{0,1\}$ :
| numéro | partie | transition (toute lettre) | final après échange |
|---|---|---|---|
| $0$ | $\{0\}$ | $3$ | non |
| $1$ | $\emptyset$ | $1$ | oui |
| $2$ | $\{1\}$ | $2$ | non |
| $3$ | $\{0,1\}$ | $3$ | non |
Depuis l'état initial $0$, seuls $0$ et $3$ sont accessibles, et aucun n'est final (l'unique état final, $\emptyset$, est inaccessible) :
$$\boxed{\mathcal{L}(\mathcal{B}_5)=\emptyset=L_\varphi}$$
C'est cohérent : $\varphi(x_2)$ équivaut à $\forall x_1.\,x_1=x_2$, fausse pour tout $x_2$.
> [!PIEGE]
> Complémenter $\mathcal{B}_1$ sans le compléter donnerait le langage vide dès l'étape 2, et tout le déroulé serait faux.
> [!JURY]
> Quand l'énoncé demande de détailler les automates intermédiaires, la seule conclusion, même juste, ne suffit pas : chaque étape doit être montrée, avec ses hypothèses (ici l'automate choisi pour la feuille).
### Question 28
> [!INDICATION]
> Traduisez littéralement la description de Q26 par un filtrage sur le constructeur de la formule.
#### Solution
```ocaml
let rec automate_formule phi n =
match phi with
| Egale (V i, V j) -> automate_egalite n i j
| Egale (V i, Plus (j, k)) -> automate_somme n j k i (* v_j + v_k = v_i *)
| Egale (Plus _, _) -> failwith "formule non sous forme simple"
| Non psi -> complementaire (automate_formule psi n)
| Et (psi1, psi2) ->
intersection (automate_formule psi1 n) (automate_formule psi2 n)
| Existe (i, psi) ->
sans_zero (automate_existe (automate_formule psi n) i)
```
Chaque appel récursif porte sur une sous-formule stricte : la fonction termine. Toutes les opérations conservent le champ `n`, donc l'alphabet $\Sigma_n$.
> [!PIEGE]
> Oublier `sans_zero` dans le cas `Existe` : l'algorithme se trompe dès qu'un témoin demande plus de bits que le mot n'en a.
### Question 29
> [!INDICATION]
> Récurrence structurelle sur la formule. Énoncez d'abord, à part, ce que deviennent les valeurs $v_k$ quand on ajoute des lettres nulles à droite.
> [!INDICATION]
> Les cas des atomes, de $\neg$ et de $\wedge$ découlent des spécifications des fonctions utilisées. Le seul cas délicat est $\exists$ : traitez les deux inclusions séparément.
> [!INDICATION]
> Pour l'inclusion difficile du cas $\exists$, il faut fabriquer un mot qui code le témoin : choisissez sa longueur pour que la valeur tienne.
#### Solution
On montre que, pour toute formule $\varphi$ sous forme simple de variables parmi $x_1,\dots,x_n$, l'automate renvoyé reconnaît $L_\varphi$ (les lignes des variables non libres y sont quelconques).
**Lemme 1.** $v_k(m\mathbf{0}^j)=v_k(m)$ pour tout $k$ (bits de poids fort nuls), donc $a_{m\mathbf{0}^j}=a_m$.
**Lemme 2.** Pour $m$, $i$ et $N\in\mathbb{N}$, il existe $j$ et $w$ avec $|w|=|m|+j$, $\pi_k(w)=\pi_k(m\mathbf{0}^j)$ pour $k\ne i$, et $v_i(w)=N$ : on choisit $2^{|m|+j}>N$ et on écrit $N$ en binaire sur la ligne $i$.
**Induction.**
- **Atomes** : par les spécifications de `automate_egalite` et `automate_somme`, le langage est $\{v_i=v_j\}$ ou $\{v_j+v_k=v_i\}$, exactement $L_\varphi$.
- **$\neg\psi$** : par Q12 et l'hypothèse d'induction, le langage est $\Sigma_n^*\setminus L_\psi=L_{\neg\psi}$ ($\neg\psi$ et $\psi$ ont les mêmes variables libres).
- **$\psi_1\wedge\psi_2$** : intersection $L_{\psi_1}\cap L_{\psi_2}=L_\varphi$, le même mot fournissant les valeurs des variables communes.
- **$\exists x_i.\psi$** : par Q25, la projection reconnaît $(L_\psi)_{\exists i}$ ; après `sans_zero`, $m$ est accepté si et seulement s'il existe $j$ avec $m\mathbf{0}^j\in(L_\psi)_{\exists i}$.
- ($\subseteq$) Si $w\in L_\psi$ coïncide avec $m\mathbf{0}^j$ hors de la ligne $i$, le lemme 1 donne $v_k(w)=v_k(m)$ pour $k\ne i$ ; $\psi$ est donc vraie quand $x_i$ vaut $v_i(w)$ et les autres variables libres leurs valeurs dans $m$ : $m\in L_\varphi$.
- ($\supseteq$) Si $m\in L_\varphi$, il existe $N$ rendant $\psi$ vraie avec $x_i\mapsto N$ ; le lemme 2 fournit $w$, dont l'assignation est exactement celle-là (lemme 1), donc $w\in L_\psi$ et $m$ est accepté.
La forme simple n'a pas d'autre constructeur : **l'algorithme est correct**.
> [!METHODE]
> Pour prouver un compilateur « formule → objet », on fait une induction structurelle dont chaque cas invoque la spécification de l'opération utilisée. Les lemmes techniques communs (ici l'invariance par zéros) se démontrent avant, une fois pour toutes.
> [!PIEGE]
> Confondre le mot et l'assignation : la sémantique ne dépend que des lignes des variables libres. C'est pour cela qu'effacer la ligne $i$ traduit correctement la liaison de $x_i$.
### Question 30
> [!INDICATION]
> Si la formule est close, de quoi dépend l'appartenance d'un mot à $L_\varphi$ ? Quels langages sont alors possibles ?
> [!INDICATION]
> Il suffit alors de tester un seul mot bien choisi ; lequel se lit directement sur l'automate ?
#### Solution
```ocaml
let est_vraie phi n =
let a = automate_formule phi n in
a.finaux.(0) (* l'état initial est l'état 0 *)
```
**Correction.** Si $\varphi$ est close, l'assignation $a_m$ est vide pour tout $m$, donc $L_\varphi=\Sigma_n^*$ si $\varphi$ est vraie et $L_\varphi=\emptyset$ sinon. Par Q29 l'automate reconnaît $L_\varphi$. Sans transition spontanée, $\varepsilon$ est accepté si et seulement si l'état initial $0$ est final. Donc `a.finaux.(0)` vaut `true` si et seulement si $\varphi$ est vraie. Le coût est celui de la construction (exponentiel à chaque négation) ; la lecture finale est immédiate. **Tautologie-Presburger est décidable.**
> [!METHODE]
> Un test de vide par parcours de graphe depuis l'état initial (avec marquage des états vus) conviendrait aussi ; la remarque sur la dichotomie $\emptyset$ / $\Sigma_n^*$ permet de s'en passer, à condition de l'écrire.
## Bilan
**Méthodes à retenir.**
- **Coder des entiers par des mots** poids faible en tête : ajouter des zéros à droite ne change pas les valeurs, et la retenue de l'addition se propage dans le sens de lecture.
- **Prouver le langage d'un automate** : donner le sens de chaque état et le démontrer par récurrence sur la longueur, en équivalence (Q4, Q15).
- **Déterminiser, compléter, complémenter** : l'échange des finaux exige un automate déterministe complet ; le produit d'automates donne l'intersection sans hypothèse (Q9 à Q13).
- **Lemme de l'étoile** avec un préfixe neutre de longueur au moins le nombre d'états (Q16).
- **Normaliser une syntaxe** par induction structurelle, avec des variables fraîches et un lemme de « témoin unique » (Q19).
- **Déduction naturelle** : appliquer les introductions d'abord en lisant de bas en haut, et écrire les instances des règles à paramètres (Q20 à Q22).
- **Compiler une formule en automate** et le prouver par induction, la quantification existentielle demandant projection puis fermeture par zéros (Q26 à Q29).
**Prérequis à revoir.** Construction par sous-ensembles et sa preuve, automate produit, lemme de l'étoile, règles de la déduction naturelle (en particulier $\vee e$, $\exists e$ et leurs conditions de bord), réductions polynomiales, filtrage OCaml sur listes et types sommes.
**Questions transposables.** L'automate de l'addition binaire et sa preuve, la non-reconnaissabilité d'un langage arithmétique, la déterminisation programmée avec numérotation des parties, le complémentaire d'un automate non complet, la réduction de SAT vers un problème logique plus expressif : ces exercices reviennent sous d'autres habillages dans de nombreux sujets d'informatique théorique.
Aide sur le corrigé
Connectez-vous pour demander une explication.