Corrigé X-ENS 2026 Informatique C MPI — Partie I (Q1 à Q6) : Systèmes de transitions, propriétés de sûreté

Q1. (a) $\Rightarrow$ (b). Soit $I$ un invariant, $s\in I$ et $\pi :s=s_0\stackrel{{\alpha }_0}{\to }{s}_1\stackrel{{\alpha }_1}{\to }\cdots$ une exécution infinie. Par récurrence sur $i$, $s_i\in I$ : c'est vrai pour $i=0$, et si $s_i\in I$, comme ${\alpha }_i\in \mathcal{D}(s_i)$, la définition d'un invariant donne $s_{i+1}=\delta (s_i,{\alpha }_i)\in I$. Donc $\mathrm{trace}(\pi )\in I^{\omega }$, et $s\models I^{\omega }$. (Ce sens n'utilise pas l'absence d'état terminal.)

(b) $\Rightarrow$ (a). Soit $s\in I$, $\alpha \in \mathcal{D}(s)$ et $s^{\prime }=\delta (s,\alpha )$. Comme $T$ n'a aucun état terminal, on construit une exécution infinie issue de $s^{\prime }$ : on pose $s_0^{\prime }=s^{\prime }$ et, $s_i^{\prime }$ étant construit, on choisit ${\alpha }_i^{\prime }\in \mathcal{D}(s_i^{\prime })\ne \varnothing$ et $s_{i+1}^{\prime }=\delta (s_i^{\prime },{\alpha }_i^{\prime })$. Alors $s\stackrel{\alpha }{\to }{s}_0^{\prime }\stackrel{{\alpha }_0^{\prime }}{\to }{s}_1^{\prime }\cdots$ est une exécution infinie issue de $s$, de trace $s{s}^{\prime }{s}_1^{\prime }\dots$ Par (b), cette trace est dans $I^{\omega }$ : sa deuxième lettre $s^{\prime }$ est dans $I$. Donc $I$ est un invariant.

Ce que le correcteur attend : l'hypothèse « sans état terminal » sert exactement dans le second sens. Sans elle, l'équivalence tombe : avec $S=\{x,y\}$ et la seule transition $x\to y$ ($y$ terminal), $I=\{x\}$ vérifie (b), puisqu'aucune exécution infinie ne part de $x$, sans être un invariant.

Q2. On fixe deux états distincts $s\ne s^{\prime }$.

• $P_1$ est de sûreté. Si $w\notin P_1$, tout état de $S$ apparaît dans $w$ ; comme $S$ est fini, un préfixe fini $\hat{w}$ de $w$ contient déjà tous les états (on prend le préfixe s'arrêtant à la plus grande des positions de première occurrence). Tout mot $\hat{w}{w}^{\prime }$ contient alors tous les états : $\hat{w}{w}^{\prime }\notin P_1$.
• $P_2$ n'est pas de sûreté. $w=sss\cdots \notin P_2$ ($s^{\prime }$ n'y apparaît pas), mais pour tout préfixe $\hat{w}$, en écrivant $S=\{e_1,\dots ,e_k\}$, le mot $\hat{w}(e_1{e}_2\cdots e_k{)}^{\omega }$ contient chaque état une infinité de fois : il est dans $P_2$.
• $P_3$ n'est pas de sûreté. $w=(e_1\cdots e_k{)}^{\omega }\notin P_3$ (tout état y est infiniment souvent), mais pour tout préfixe $\hat{w}$, le mot $\hat{w}{s}^{\omega }$ contient $s^{\prime }$ un nombre fini de fois : il est dans $P_3$.

L'hypothèse $|S|⩾2$ sert pour $P_2$ et $P_3$ : avec un seul état $s$, $S^{\omega }=\{s^{\omega }\}$, $P_2=S^{\omega }$ et $P_3=\varnothing$ seraient de sûreté (trivialement).

Q3. On note $d(u)=|u{|}_a-|u{|}_b$ ; chaque lettre change $d$ de $\pm 1$ ($a$ : $+1$, $b$ : $-1$), et $d(\epsilon )=0$. L'alphabet est $S=\{a,b\}$ (le sujet écrit ${\Sigma }^{\ast }$ pour $S^{\ast }$). Chacune des quatre propriétés s'écrit « tout préfixe $u$ de $w$ vérifie $c(u)$ ». Lemme : si tous les préfixes de $u$ (lui compris) vérifient $c$, alors $u$ n'est pas interdit, car on exhibe un prolongement infini qui reste dans la bande autorisée (ci-dessous) ; et si un préfixe de $u$ viole $c$, tout mot infini prolongeant $u$ est hors de $P_i$, donc $u$ est interdit. Par conséquent $u$ est un préfixe interdit minimal si et seulement si $u$ viole $c$ et aucun de ses préfixes stricts ne la viole : la première violation a lieu à la dernière lettre.