Centrale 2022 - Option informatique

Sujet

Corrigé du sujet d'informatique (option informatique) du concours Centrale-Supélec 2022, filière MP. L'énoncé n'est pas reproduit ici : il faut le consulter à côté de ce corrigé. Les questions sont numérotées comme dans l'énoncé.

Mots et automates

Miroir d'un mot et automate transposé

Question 1.

Corrigé

On va décrire ces langages par des expressions rationnelles : \(L_1\) est dénoté par \((a|b)^* a b a^*\) et \(\tilde{L}_1\) par \(a^* b a (a|b)^*\).

Question 2.

Corrigé

Question 3.

Corrigé

On pose \(I' = F\), \(F' = I\) et pour \(q,q' \in Q\), \(a \in \Sigma\), \((q,a,q') \in T \iff (q',a,q) \in T'\).

Soit encore, \(T' = \enscomp{(q',a,q)}{(q,a,q') \in T}\). On a donc \(q \xrightarrow{a} q'\) dans \(A\) ssi \(q' \xrightarrow{a} q\) dans \(\tilde{A}\) et, par une récurrence rapide sur la longueur des chemins, on en déduit qu'un chemin est dans \(A\) ssi son renversement est dans \(\tilde{A}\).

Comme on a échangé les états finaux et initiaux, on en déduit que \(L_{\tilde{A}} = \tilde{L}\).

Question 4.

Corrigé

let transpose a =
    {
        nb = a.nb;
        init  = a.final;
        final = a.init;
        trans = List.map
            (fun (q,a,q') -> (q',a,q)) a.trans
    }

Question 5.

Corrigé

La complexité de cette fonction est déterminée par le parcours de la table de transitions, on est donc en \(O(|T|)\).

Palindromes et rationalité

Question 6.

Corrigé

let palindrome w =
    let n = String.length w in
    let pal = ref true in
    for i = 0 to n / 2 - 1 do
        if w.[i] <> w.[n-i-1]
        then pal := false
    done;
    !pal

Question 7.

Corrigé

Si \(\Sigma = \{ a\}\) alors \(\mathop{Pal}(\Sigma) = \Sigma^*\) car tous les mots sont des palindromes. Or, \(\Sigma^*\) est évidemment rationnel.

Question 8.

Corrigé

S'il existe \(a, b \in \Sigma\) tels que \(a \neq b\), on sait que le langage \(L = \enscomp{ a^n b a^n }{ n \in \N}\) n'est pas rationnel (voir cours).

Or, \(a^* b a^*\) est rationnel et si \(\mathop{Pal}(\Sigma)\) était rationnel, alors par stabilité des langages rationnels par intersection, on aurait \(\mathop{Pal}(\Sigma) \cap a^* b a^* = L\) rationnel. Donc, \(\mathop{Pal}(\Sigma)\) est non rationnel.

Question 9.

Corrigé

\(L_{q,q'}\) est directement reconnu par l'automate \((Q, \{ q \}, \{ q' \},T)\).

On a

\[ L_A = \bigcup_{q \in I} \bigcup_{q' \in F} L_{q,q'} \]

car un mot reconnu est l'étiquette d'un chemin d'un état de \(I\) vers un état de \(F\).

Question 10.

Corrigé

On remarque que \((\Sigma^2)^*\) est l'ensemble des mots de longueur paire car ceux-ci peuvent se découper en facteurs disjoints de longueur 2.

On a \(\widetilde{u\tilde{u}} = \widetilde{\tilde{u}} \tilde{u} = u \tilde{u}\) et \(|u \tilde{u}| = 2|u|\) est pair, donc \(\enscomp{u \tilde{u}}{u \in \Sigma^*} \subset \mathop{Pal}(\Sigma) \cap (\Sigma^2)^*\).

Soit \(w \in \mathop{Pal}(\Sigma) \cap (\Sigma^2)^*\), si on note \(w = a_1 \dots a_{2p}\) et \(w' =a_1 \dots a_{p}\), \(w'' = a_{p+1} \dots a_{2p}\), comme \(w\) est un palindrome, \(a_i = a_{2p-i+1}\) et donc \(w'' = \tilde{w'}\). Ainsi, \(w = w' w'' = w' \tilde{w'}\) et on en déduit l'autre inclusion.

Question 11.

Corrigé

\[ D(a^* b) =\enscomp{a^n b b a^n}{ n \in \N} \]

Ici, on remarque que les palindromes dans \(a^* b^* a^*\) sont de la forme \(a^n b^m a^n\) et ils sont donc de longueur paire ssi \(m\) est pair. On en déduit qu'ils s'écrivent alors \(a^n b^{2p} a^n = a^n b^p \widetilde{a^n b^p}\).

\[ R(a^* b^* a^*) = \enscomp{a^n b^p}{n \in \N, p \in \N} = a^* b^* \]

Question 12.

Corrigé

On remarque que \(a^*b\) est rationnel mais \(D(a^*b)\) ne l'est pas, on se ramène encore à \(\enscomp{a^n b^n}{n \in \N}\).

On peut considérer l'automate où on avance en même temps dans \(A\) depuis un état initial dans un sens et depuis un état final dans l'autre sens. On pose ainsi \(A_R = (Q \times Q, I \times F, \Delta, T_R)\) où \(\Delta = \enscomp{(q,q)}{q \in Q}\) et

\[ T_R = \enscomp{ ((q_1,q_2), a, (q'_1,q'_2)) } { (q_1,a,q'_1) \in T \wedge (q'_2,a,q_2) \in T} \]

Un mot \(w\) est alors reconnu par \(A_R\) ssi il existe \(i \in I\), \(f \in F\) et \(q \in Q\) avec \(i \xrightarrow{w} q\) et \(q \xrightarrow{\tilde{w}} f\) dans \(A\), c'est-à-dire ssi \(w \tilde{w} \in L\).

On peut aussi remarquer que si \(w = a_1 \dots a_n \in R(L)\), on a un chemin

\[ i \xrightarrow{a_1} \dots \xrightarrow{a_n} q \xrightarrow{a_n} \dots \xrightarrow{a_1} f \]

pour \(i \in I\) et \(f \in F\). On a donc \(w \in L_{i,q}\) et \(\tilde{w} \in L_{q,f} \iff w \in \widetilde{L_{q,f}}\). Réciproquement, un tel \(w\) vérifie \(w \tilde{w} \in L\).

Ainsi,

\[ R(L) = \bigcup_{i \in I} \bigcup_{f \in F} \bigcup_{q \in Q} L_{i,q} \cap \widetilde{L_{q,f}} \]

qui est rationnel par stabilité par unions finies et intersection des langages rationnels (et par miroir, question 3).

Déterminisation

Question 13.

Corrigé

Question 14.

Corrigé

L'automate miroir est :

Automate miroir : transitions retournées, \(q_3\) initial et \(q_0\) final.

On applique la méthode vue en classe :

\[ \begin{array}{cccc} & & a & b \\ \hline \rightarrow & e_0 = \{ q_3 \} & e_1 & \emptyset \\ & e_1 = \{ q_2 \} & \emptyset & e_2 \\ * & e_2 = \{ q_0 \} & \emptyset & e_3 \\ * & e_3 = \{ q_0, q_1 \} & e_2 & e_3 \\ \end{array} \]

Automate déterminisé (états \(e_0\) à \(e_3\) du tableau).

Question 15.

Corrigé

L'automate miroir est :

Automate miroir : transitions retournées, \(e_2\) et \(e_3\) initiaux, \(e_0\) final.

On déterminise :

\[ \begin{array}{cccc} & & a & b \\ \hline \rightarrow & q_0 = \{ e_2, e_3 \} & q_1 & q_2 \\ & q_1 = \{ e_3 \} & \emptyset & q_0 \\ & q_2 = \{ e_1, e_2, e_3 \} & q_3 & q_2 \\ * & q_3 = \{ e_0, e_3 \} & \emptyset & q_0 \end{array} \]

Automate déterminisé (états \(q_0\) à \(q_3\) du tableau).

Question 16.

Corrigé

On sait que déterminiser préserve le langage, donc \(L_{A_4} = L_{\widetilde{A_3}} = \widetilde{L_{A_3}} = \widetilde{ L_{\widetilde{A_2}} } = \widetilde{ \widetilde{ L_{A_2} } } = L_{A_2}\).

Question 17.

Corrigé

let rec supprimer l =
    match l with
    | [] -> []
    | t::q -> let q' = supprimer q in
        if List.mem t q' then q' else t::q'

Question 18.

Corrigé

On effectue un parcours de la liste et à chaque élément, on appelle List.mem qui est également linéaire. On a donc un algorithme en \(O(n^2)\) où \(n\) est le nombre d'éléments de la liste.

Question 19.

Corrigé

On utilise un tableau pow précalculé tel que pow.(i) vaut \(2^i\) pour \(0 \le i \le 20\).

let pow =
    let t = Array.make 21 1 in
    for i = 1 to 20 do
        t.(i) <- t.(i-1) * 2
    done;
    t

let est_dans q k =
    (k / pow.(q)) mod 2 = 1

Question 20.

Corrigé

Deux versions possibles :

let numero l =
    let rec aux l =
        match l with
        | [] -> 0
        | i::q -> pow.(i) + aux q
    in
    aux (supprimer l)

let numero l =
    List.fold_left (+) 0
        (List.map (fun i -> pow.(i)) (supprimer l))

Question 21.

Corrigé

let rec intersecte l k =
    match l with
    | [] -> false
    | t::q -> est_dans t k || intersecte q k

Question 22.

Corrigé

let etat_suivant k t =
    let suivants c =
        List.map (fun (_,_,q) -> q)
            (List.filter (fun (q,a,_) -> c = a && est_dans q k) t) in
    let la = suivants 'a' in
    let lb = suivants 'b' in
    (numero la, numero lb)

Question 23.

Corrigé

let rec cherche k l =
    match l with
    | [] -> -1 (* beurk *)
    | (k',v)::q when k' = k -> v
    | _::q -> cherche k q

Question 24.

Corrigé

Note. Cette fonction est beaucoup trop délicate pour être donnée ainsi sans plus d'indications.

let determinise a =
    let corres = ref [] in
    let final = ref [] in

    let int_of_num k =
        let v = cherche k !corres in
        if v = -1
        then let v' = List.length !corres in
            corres := (k, v') :: !corres;
            if intersecte a.final k
            then final := v' :: !final;
            v'
        else v
    in

    let i = numero a.init in
    let init = int_of_num i in

    let rec parcours q =
        let nq = int_of_num q in
        let la, lb = etat_suivant q a.trans in
        let res = ref [] in
        if cherche la !corres = -1
        then res := !res @ parcours la;
        if cherche lb !corres = -1
        then res := !res @ parcours lb;
        (nq,'a',int_of_num la)
            ::(nq,'b',int_of_num lb)::!res
    in
    let trans= parcours i in

    {
        nb = List.length !corres;
        init = [init];
        final = !final;
        trans = trans
    }

L'automate obtenu est complet : l'ensemble vide (numéro \(0\)) est un état puits dès qu'il est accessible. Appliquée au miroir de l'automate de la question 13, elle produit ainsi les quatre états de la question 14 plus l'état puits.

Question 25.

Corrigé

On effectue autant d'appels à parcours que d'états dans \(A_{det}\), soit \(N\) appels. Dans chacun :

• etat_suivant parcourt la liste des transitions puis appelle numero, donc supprimer, sur des listes de longueur au plus \(|T|\) : \(O(|T|^2)\) opérations ;
• les appels à cherche parcourent corres, de longueur au plus \(N\) : \(O(N)\) (de même pour les concaténations @) ;
• intersecte coûte \(O(n)\).

On est donc en \(O(N(|T|^2 + N))\). Comme \(N = O(2^n)\), c'est coûteux en pire cas.

Brzozowski

Remarque

Dans cette partie, il semble y avoir un problème apparent de notation vu que \(\delta^* : Q' \times \Sigma \rightarrow Q'\). Cependant, \(Q'= \mathcal{P}(Q)\) et c'est ainsi qu'il faut le comprendre. Par contre, il y a bien une erreur avec l'emploi de \(\{I\}\) à la place de \(I\).

Question 26.

Corrigé

Comme l'automate miroir est accessible, cela entraîne que l'automate lui-même est co-accessible, il existe ainsi un chemin de tout état vers un état final qu'il suffit de renverser pour en déduire \(w\). Plus précisément :

Comme \(q \in \delta^*(I,u)\) dans le déterminisé, cela signifie qu'il y a forcément un chemin \(q \xrightarrow{\tilde{u}} i\) avec \(i \in I\) dans \(\tilde{A}\). Comme \(q\) est accessible depuis un état initial \(f\) de cet automate accessible, on sait qu'il existe \(w\) étiquette d'un chemin \(f \xrightarrow{w} q\). On a donc \(w \widetilde{u} \in \widetilde{L}\), donc \(u \widetilde{w} \in L\).

Question 27.

Corrigé

Soit \(q \in \delta^*(I,u)\). Par la question précédente, il existe \(w \in \Sigma^*\) tel que \(f \xrightarrow{\tilde{w}} q\) dans \(\widetilde{A}\), où \(f\) est l'unique état initial de \(\widetilde{A}\), et \(uw \in L\). Donc \(w \in u^{-1} L = v^{-1} L\) et \(v w \in L\). On en déduit deux chemins

\[ f \xrightarrow{\tilde{w}} q' \xrightarrow{\tilde{v}} i' \in I \qquad f \xrightarrow{\tilde{w}} q \xrightarrow{\tilde{u}} i \in I \]

dans \(\widetilde{A}\). Mais comme cet automate est déterministe, on a nécessairement \(q = q'\). Or, comme \(q \xrightarrow{\tilde{v}} i' \in I\), c'est qu'on a bien \(q \in \delta^*(I,v)\).

Par symétrie, on a bien l'égalité.

Question 28.

Corrigé

C'est direct ici car \(B = \widetilde{\widetilde{B}}\) est déterministe et accessible (c'est un déterminisé), donc \((\widetilde{B})_{det}\) vérifie \(*\) par la question précédente.

Remarque

Le sujet n'en dit pas plus, mais la propriété \(*\) signifie que les états de l'automate sont bien minimaux car tous les états sont bien distingués les uns des autres : tous les états permettent de reconnaître depuis ceux-ci des mots différents.

Question 29.

Corrigé

let minimal a =
    determinise (transpose (determinise (transpose a)))

Expression rationnelle associée à un automate

Cette partie (questions 30 à 43) n'est pas corrigée.

Automate des dérivées d'Antimirov

Question 44.

Corrigé

\[ \begin{array}{rcl} \partial_a((ab|b)^*ba) & = & \partial_a(ab|b) . \{ (ab|b)^* \} . \{ ba \} \cup \partial_a(ba) \\ &=&(\partial_a(a) \{b\} \cup \partial_a(b)) . \{ (ab|b)^* \} . \{ ba \} \cup \partial_a(b) \{a\} \\ &=& (\{\epsilon\} \{b\} \cup \emptyset ) \{ (ab|b)^* ba \} \cup \emptyset \{ a \} \\ &=& \{ b (ab |b)^* b a \} \end{array} \]

\[ \begin{array}{rcl} \partial_b((ab|b)^*ba) & = & \partial_b(ab|b) . \{ (ab|b)^* \} . \{ ba \} \cup \partial_b(ba) \\ &=&(\partial_b(a) \{b\} \cup \partial_b(b)) . \{ (ab|b)^* \} . \{ ba \} \cup \partial_b(b) \{a\} \\ &=& (\emptyset \{b\} \cup \{\epsilon\} ) \{ (ab|b)^* ba \} \cup \{ \epsilon \}\{ a \} \\ &=& \{ (ab|b)^* ba, a \} \end{array} \]

Question 45.

Corrigé

On construit la table des dérivations comme dans le cas de la table de l'automate des parties.

\[ \begin{array}{cc|c|c} & & \partial_a & \partial_b \\ \hline \rightarrow & (ab|b)^* ba & b (ab | b)^* ba & (ab|b)^*ba, a \\ & b (ab|b)^* ba & \emptyset & (ab|b)^* ba \\ & a & \epsilon & \emptyset \\ * & \epsilon & \emptyset & \emptyset \\ \end{array} \]

Automate dont les états sont les dérivées de \((ab|b)^*ba\).

Question 46.

Corrigé

\(w \in (uv)^{-1} L \iff u v w \in L \iff v w \in u^{-1} L \iff w \in v^{-1} (u^{-1} L) = v^{-1} u^{-1} L\).

Question 47.

Corrigé

Par la question précédente et une récurrence sur \(|w|\), on a \(\mathcal{L}(\partial_w (E)) = w^{-1} \mathcal{L}(E)\). On conclut alors directement par passage à l'union :

\[ \mathcal{L}(\partial_w (S)) = \mathcal{L}(\bigcup_{E \in S} \partial_w (E)) = \bigcup_{E \in S} \mathcal{L}(\partial_w (E)) = \bigcup_{E \in S} w^{-1} \mathcal{L}(E) = w^{-1} \bigcup_{E \in S} \mathcal{L}(E) =w^{-1} \mathcal{L}(S) \]

Question 48.

Corrigé

Si on a un chemin \(E \xrightarrow{a_1} \dots \xrightarrow{a_n} q\) avec \(w = a_1 \dots a_n\) alors, par construction de l'automate, on a \(q \in \partial_w(E)\). Réciproquement, tout \(q \in \partial_w(E)\) est l'extrémité d'un tel chemin.

Il s'agit d'une récurrence facile sur \(|w|\) : les transitions issues d'un état \(E'\) en lisant \(a\) mènent exactement aux éléments de \(\partial_a(E')\), et \(\partial_{w a}(E) = \bigcup_{E' \in \partial_w(E)} \partial_a(E')\).

Question 49.

Corrigé

Soit \(w \in \mathcal{L}(E)\), on a donc \(\epsilon \in w^{-1} \mathcal{L}(E) = \mathcal{L}(\partial_w (E) )\) ce qui signifie qu'il existe un état acceptant dans \(\partial_w(E)\), l'ensemble des états accessibles depuis \(E\) en lisant \(w\). On vient de voir que l'automate d'Antimirov reconnaît alors \(w\).

Réciproquement, si \(w\) est reconnu, cela signifie qu'il existe une expression rationnelle \(E'\) telle que \(\epsilon \in \mathcal{L}(E')\) avec \(E' \in \partial_w(E)\) donc \(\epsilon \in \mathcal{L}(\partial_w(E)) = w^{-1} \mathcal{L}(E)\), soit encore \(w \in \mathcal{L}(E)\).

Note. Il y a un raisonnement par équivalence possible ici.

Question 50.

Corrigé

On raisonne par induction sur \(E\). Ça se fait bien.