Corrigé Mines-Ponts 2025 Informatique option MP — Partie 2 (Q10 à Q13) : Séparabilité par rapport à un langage

Un langage régulier $L\subseteq {\Sigma }^{\ast }$, inconnu, est fixé jusqu'à la fin du sujet. On l'interroge par un oracle : requête d'appartenance (« $w\in L$ ? ») et requête d'équivalence (« l'automate $\mathcal{A}$ reconnaît-il $L$ ? »), qui en cas de réponse négative fournit un contre-exemple $c$, mot sur lequel $\mathcal{A}$ se trompe.

(* module Oracle *)
type answer = Yes | Counterexample of word
val mem : word -> bool
val equiv : automaton -> answer
type disc = word          (* rôle de discriminant, mot surligné dans le sujet *)

$1_{\Lambda }$ désigne l'indicatrice d'un langage $\Lambda$. Deux mots $u_1,u_2$ sont séparés par $\overline{v}$ relativement à $\Lambda$ si $1_{\Lambda }(u_{1}v)\ne 1_{\Lambda }(u_{2}v)$ ; $v$ est alors un discriminant. Ils sont séparables si un discriminant les sépare, inséparables sinon, ce que l'on note $u_1{\equiv }_{\Lambda }{u}_2$.

Q10. Écrire separated_by (u1:word) (u2:word) (v:disc) : bool, qui teste si $v$ sépare $u_1$ et $u_2$ relativement à $L$.
Q11. Montrer que ${\equiv }_{\Lambda }$ est une relation d'équivalence sur ${\Sigma }^{\ast }$.
Q12. Soit $\mathcal{A}=(Q,q_0,\delta ,1_F)$ un automate de langage $L_{\mathcal{A}}$, et $u_1,u_2$ tels que ${\delta }^{\ast }(q_0,u_1)={\delta }^{\ast }(q_0,u_2)$. Montrer que $u_1{\equiv }_{L_{\mathcal{A}}}{u}_2$.
Q13. Citer un théorème liant langages réguliers et langages reconnus par automate ; en déduire avec Q12 que ${\equiv }_L$ n'a qu'un nombre fini de classes.