Corrigé Mines-Ponts 2025 Informatique option MP — Partie 4 (Q22 à Q28) : Apprentissage d'un automate minimal par cribles

Lemme préliminaire.

Soit $T$ un crible et $\mathcal{A}$ son automate associé. (a) Pour tout état $\underline{w}$, $1_F(w)=1_L(w)$. (b) Pour tout mot $u$, $1_L(u)=1_L(\lfloor u\rfloor )$.

Preuve. (a) Par accessibilité, le criblage de $w$ aboutit à la feuille $\underline{w}$ ; il passe donc dans le sous-arbre gauche si et seulement si son premier pas, à la racine $\overline{\epsilon }$, va à gauche, c'est-à-dire si et seulement si $w\epsilon =w\in L$. Ainsi $w\in F⟺w\in L$. (b) $\lfloor u\rfloor$ est une étiquette de feuille, donc $\lfloor \lfloor u\rfloor \rfloor =\lfloor u\rfloor$ par accessibilité : $u$ et $\lfloor u\rfloor$ ont le même criblat, et Q21 (un crible est démêlant) donne $1_L(u)=1_L(\lfloor u\rfloor )$.

Q22. Les transitions criblent $wx$ (Q16) ; les états finals sont les feuilles du fils gauche (Q14), liste calculée une seule fois, à la construction :

let automaton_of_disctree (t:disctree) : automaton =
  { initial = [] ;
    transitions = (fun w x -> sift t (w @ [x])) ;
    finals = (match t with
              | Node (g, _, _) -> let gauche = states_of_disctree g in
                                  (fun w -> List.mem w gauche)
              | Leaf _ -> (fun _ -> false))   (* exclu : crible démêlant *)
  }

Le mot $\epsilon$ est [] ; w @ [x] est le mot $wx$, et sift t renvoie $\lfloor wx\rfloor$, qui est bien une étiquette de feuille, donc un état. finals est une fonction, comme l'exige le type (même remarque du jury qu'en Q7). Par le lemme (a), on pourrait aussi écrire finals = Oracle.mem, mais la définition du sujet ne coûte aucune requête. (Exécutée sur ${\mathcal{T}}_0$ avec un oracle pour $a{b}^{\ast }a$ : on retrouve exactement les transitions de la figure, seul $\underline{aa}$ est final, et Oracle.equiv répond Yes : ${\mathcal{T}}_0$ est un crible dont l'automate reconnaît $a{b}^{\ast }a$.)

Q23. On pose une requête d'appartenance pour $\epsilon$, puis une requête d'équivalence pour l'automate ${\mathcal{A}}_1$ à un seul état $\underline{\epsilon }$, qui boucle sur lui-même, final si et seulement si $\epsilon \in L$ :

let premier_crible () : disctree =
  let vide_dans_l = Oracle.mem [] in
  let a1 = { initial = [] ; transitions = (fun _ _ -> []) ;
             finals = (fun _ -> vide_dans_l) } in
  match Oracle.equiv a1 with
  | Oracle.Yes -> failwith "L est vide ou plein"
  | Oracle.Counterexample c ->
    if vide_dans_l then Node (Leaf [], [], Leaf c)
    else Node (Leaf c, [], Leaf [])

Le contre-exemple existe : ${\mathcal{A}}_1$ reconnaît ${\Sigma }^{\ast }$ si $\epsilon \in L$ et $\varnothing$ sinon ; comme $L$ n'est ni l'un ni l'autre, l'oracle répond par un mot $c$ sur lequel ${\mathcal{A}}_1$ se trompe, donc $1_L(c)\ne 1_{L({\mathcal{A}}_1)}(c)=1_L(\epsilon )$.

L'arbre obtenu est un crible : une racine $\overline{\epsilon }$, une feuille $\underline{\epsilon }$ et une feuille $\underline{c}$, avec $c\ne \epsilon$ puisque $1_L(c)\ne 1_L(\epsilon )$. Il est démêlant, $\underline{\epsilon }$ est une feuille, et il est accessible : on crible $u\in \{\epsilon ,c\}$ en allant à gauche si et seulement si $u\in L$, et la feuille gauche est précisément celle des deux mots qui est dans $L$. Ce que le correcteur attend : un vrai crible, accessible et démêlant (le jury note que cette exigence est rarement respectée), à deux feuilles exactement. (Exécuté avec $L=a{b}^{\ast }a$ : $\epsilon \notin L$, le contre-exemple le plus court est $aa$, et l'on obtient Node (Leaf [A;A], [], Leaf []).)

Q24. Conventions. Pour $i=\gamma$, le mot $c_{\gamma }{\sigma }_{\gamma }$ est vide : ${\pi }_{\gamma }=c$, ${\tau }_{\gamma }=p_{\gamma }=\lfloor c\rfloor$ et ${\hat{\tau }}_{\gamma }={\hat{p}}_{\gamma }={\delta }^{\ast }(\underline{\epsilon },c)$. (Le sujet imprime ${\sigma }_i=c_{i+1}{c}_1\cdots c_{\gamma -1}$ ; c'est une coquille pour $c_{i+1}\cdots c_{\gamma -1}$, seule lecture compatible avec $c={\pi }_i{c}_i{\sigma }_i$.)

Côté criblat. D'après le lemme (b), $1_L({\tau }_{\gamma })=1_L(\lfloor c\rfloor )=1_L(c)$.

Côté automate. ${\hat{p}}_{\gamma }$ est l'état atteint par $\mathcal{A}$ en lisant $c$, donc $\mathcal{A}$ accepte $c$ si et seulement si ${\hat{p}}_{\gamma }\in F$, c'est-à-dire, par le lemme (a), si et seulement si ${\hat{p}}_{\gamma }\in L$ : $1_{L(\mathcal{A})}(c)=1_L({\hat{\tau }}_{\gamma })$.