<jupyter_start><jupyter_text>Table of Contents 1&nbsp;&nbsp;TP 4 - Programmation pour la préparation à l'agrégation maths option info2&nbsp;&nbsp;Remise en forme : listes associatives2.1&nbsp;&nbsp;Exercice 1 : appartient2.2&nbsp;&nbsp;Exercice 2 : insere2.3&nbsp;&nbsp;Exercice 3 : existe2.4&nbsp;&nbsp;Exercice 4 : trouve2.5&nbsp;&nbsp;Exercice 5 : supprime2.6&nbsp;&nbsp;Question bonus : avec des tables d'associations3&nbsp;&nbsp;Automates finis déterministes3.1&nbsp;&nbsp;Types de données3.2&nbsp;&nbsp;Affichage (PAS DANS LE TP)3.3&nbsp;&nbsp;Reconnaissance d'un mot3.3.1&nbsp;&nbsp;Récursivement3.3.2&nbsp;&nbsp;Itérativement3.4&nbsp;&nbsp;Deux exemples d'automates3.5&nbsp;&nbsp;Exemple de lectures3.6&nbsp;&nbsp;Complétion (DIFFICILE)3.7&nbsp;&nbsp;Complémentaire (plus dur)4&nbsp;&nbsp;Expressions régulières4.1&nbsp;&nbsp;Exercice 10 : regexp4.2&nbsp;&nbsp;Exercice 11 : deux regexp pour les deux automates A1" role="presentation" style="position: relative;">𝐴1A1A_1, A2" role="presentation" style="position: relative;">𝐴2A2A_24.3&nbsp;&nbsp;Exercice 12 : to_string4.4&nbsp;&nbsp;Exercice 13 : est_vide4.5&nbsp;&nbsp;Exercice 14 : est_fini4.6&nbsp;&nbsp;Exercice 15 : pile_ou_face4.7&nbsp;&nbsp;Exercice 16 : mot_aleatoire5&nbsp;&nbsp;Calcul de Σ𝑘∩𝐿(𝐴)\Sigma^k \cap L(A)5.1&nbsp;&nbsp;Exercice 17 : produit_cartesien5.2&nbsp;&nbsp;Liste de tous les mots de Σ𝑘\Sigma^k5.3&nbsp;&nbsp;Exercice 19 : filtre5.4&nbsp;&nbsp;Exercice 206&nbsp;&nbsp;Automate produit (PLUS DUR)6.1&nbsp;&nbsp;Exercice 21 : bijection6.2&nbsp;&nbsp;Exercice 227&nbsp;&nbsp;Conclusion  TP 4 - Programmation pour la préparation à l'agrégation maths option infoTP 4 : Automates et langages réguliers. - En OCaml.<jupyter_code>let print = Printf.printf;;
Sys.command "ocaml -version";;<jupyter_output><empty_output><jupyter_text>---- Remise en forme : listes associativesCertaines de ces fonctions sont dans la bibliothèque standard dans le module `List`, avec des fonctions contenant `assoc` dans leur nom :<jupyter_code>List.mem;;  (* appartient *)
List.assoc;;  (* trouve *)
List.mem_assoc;;  (* existe *)
List.remove_assoc;;  (* supprime *)<jupyter_output><empty_output><jupyter_text>Exercice 1 : `appartient`On propose plusieurs implémentations, toutes similaires mais de complexités différentes.Je vous laisse trouver les différences de comportement (lesquelles sont tout le temps linéaire, au mieux $\mathcal{O}(1)$ etc).<jupyter_code>(* En O(n) pour une liste de taille n (pire cas), en O(1) meilleur cas. *)
let rec appartient (x:'a) (l:'a list) : bool =
      match l with
      | [] -> false
      | y :: _ when x = y -> true
      | _ :: q -> appartient x q
;;
let liste1 = [ 1; 2; 3 ];;
let couple1 = (1, 2, 3) ;;
(* En O(n) pour une liste de taille n (pire cas), en O(1) meilleur cas. *)
let rec appartient (x:'a) (l:'a list) : bool =
      match l with
      | [] -> false
      | y :: q -> (x = y) || appartient x q
;;
(* En O(n) pour une liste de taille n (pire cas), en O(n) meilleur cas. *)
let rec appartient (x:'a) (l:'a list) : bool =
    match l with
    | [] -> false
    | y :: q -> appartient x q || x = y
;;
let appartient = List.mem;;
assert (appartient 3 [1;2;3;4;5]) ;;
assert (not (appartient 9 [1;2;3;4;5])) ;;<jupyter_output><empty_output><jupyter_text>Exercice 2 : `insere`On a envie d'écrire rapidement cela :<jupyter_code>let insere (k:'a) (v:'b) (l: ('a*'b) list) : ('a*'b) list =
    (k,v) :: l
;;<jupyter_output><empty_output><jupyter_text>Mais on peut réfléchir à la sémantique que l'on souhaite donner à cette fonction `insere` : si la clé `k` est déjà présente, doit-on échouer, ou ajouter une deuxième valeur associée à la même clé, ou écraser la valeur déjà associée à `k` ?Vous pouvez essayer d'implémenter chacun des variantes ! On construit un exemple de petite liste associative :<jupyter_code>let justiceleague = insere "Superman" "<NAME>" (insere "Batman" "<NAME>" []);;
let communaute =
    insere "Aragorn" "rodeur" (
        insere "Gandalf" "magicien" (
            insere "Gimli" "nain" (
                insere "Legolas" "elfe" (
                    insere "Frodon" "hobbit"
                    []
                )
            )
        )
    )
;;<jupyter_output><empty_output><jupyter_text>> La syntaxe est lourde, en comparaison d'un dictionnaire simple comme en Python...> ```python> communaute = { "Aragorn": "rodeur", "Gandalf": "magicien", "Gimli": "nain", "Legolas": "elfe", "Frodon": "hobbit" }> ```  Exercice 3 : `existe` Première version, "à la main" :<jupyter_code>let rec existe (cle : 'a) (l : ('a * 'b) list) : bool =
    match l with
    | [] -> false
    | (k, _) :: _ when cle = k -> true
    | _ :: q -> existe cle q
;;
assert (existe "Frodon" communaute) ;;
assert (not (existe "Boromir" communaute));;<jupyter_output><empty_output><jupyter_text>En utilisant la bibliothèque standard :<jupyter_code>let existe (cle : 'a) (l : ('a * 'b) list) : bool =
    List.exists (fun (k, _) -> cle = k) l
;;
assert (existe "Frodon" communaute) ;;
assert (not (existe "Boromir" communaute));;
let existe = List.mem_assoc;;
assert (existe "Frodon" communaute) ;;
assert (not (existe "Boromir" communaute));;<jupyter_output><empty_output><jupyter_text>Exercice 4 : `trouve`On doit déclencher une erreur si la clé n'est pas trouvée. Pour être consistent, on déclenche la même que la fonction de la bibliothèque standard, `Not_found` :<jupyter_code>List.assoc "ok" [];;
let rec trouve (cle : 'a) (l : ('a * 'b) list) : 'b =
    match l with
    | [] -> raise Not_found
    | (k, v) :: _ when cle = k -> v
    | _ :: q -> trouve cle q
;;
assert ((trouve "Gandalf" communaute) = "magicien");;
assert (try (trouve "Boromir" communaute) = "guerrier" with Not_found -> true);;<jupyter_output><empty_output><jupyter_text>Avec la bibliothèque standard :<jupyter_code>let trouve = List.assoc;;
assert ((trouve "Gandalf" communaute) = "magicien");;
assert (try (trouve "Boromir" communaute) = "guerrier" with Not_found -> true);;<jupyter_output><empty_output><jupyter_text>Exercice 5 : `supprime` On choisit la sémantique suivante : l'exception `Not_found` est levée si la clé n'est pas présente.On supprime sinon la *première* occurrence de la clé (rappel : `insere` ajoute `(cle, valeur)` même si `cle` est déjà présente).<jupyter_code>let rec supprime (cle : 'a) (l : ('a*'b) list) : ('a*'b) list =
    match l with
    | [] -> raise Not_found
    | (k, _) :: q when cle = k -> q
    | p :: q -> p :: supprime cle q
;;<jupyter_output><empty_output><jupyter_text>Par exemple :<jupyter_code>communaute;;
supprime "Gandalf" [ ];;
let fin_film_1 = supprime "Gandalf" communaute;;
let dans100ans = supprime "Frodon" communaute;;
let debut_film_3 = insere "Gandalf" "magicien blanc" fin_film_1;;<jupyter_output><empty_output><jupyter_text>Question bonus : avec des tables d'associationsLa bibliothèque standard fournit le module [`Map`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.htmlVALMake).Il faut au préalable créer le bon module (syntaxe un peu difficile, avec un *foncteur*).<jupyter_code>module M = Map.Make ( struct
       type t = int
       let compare = compare
    end);;

let t : string M.t = (M.add 1 "1" (M.add 2 "2" (M.add 3 "3" M.empty)));;
let _ = M.mem 1 t;;
let _ = M.mem 2 t;;
let _ = M.mem 4 t;;

let _ = M.find 1 t;;
let _ = M.find 2 t;;
let _ = M.find 4 t;;

let _ = M.remove 1 t;;
let _ = M.remove 2 t;;
let _ = M.remove 4 t;;<jupyter_output><empty_output><jupyter_text>---- Automates finis déterministes  Types de donnéesLes listes d'association sont utilises pour stocker les transitions : pour chaque état, on stocke une liste de règle associant une lettre lue à l'état d'arrivée de la transition.<jupyter_code>type ('a, 'b) assoc = ('a * 'b) list;;
type lettre = A | B | C;;

type mot = lettre list;; (* [lettre array] marche aussi bien ! *)
type langage = mot list;;
type etat = int;;
(* Automate fini déterministe *)
type afd = {
    taille : int;
    initial : etat;
    finals : etat list;
    (* on peut aussi utiliser : *)
    (* transition : (etat, (lettre, etat) assoc) assoc; *) (* comme une fonction q -> a -> q' *)
    (* transition : ((etat, lettre), etat) assoc; *) (* comme une fonction (q, a) -> q' *)
    transition : (lettre, etat) assoc array
};;<jupyter_output><empty_output><jupyter_text>Affichage (PAS DANS LE TP)On va utiliser le [langage dot](https://graphviz.readthedocs.io/en/stable/manual.htmlusing-raw-dot) pour afficher facilement des graphes, et donc ici, des automates.Plutôt que d'utiliser une bibliothèque, on va écrire une fonction `dot` qui transforme un automate fini déterministe a en un fichier `out.dot` qui est ensuite converti en SVG (pour être affiché ici).<jupyter_code>let string_of_lettre = function
    | A -> "A"
    | B -> "B"
    | C -> "C"
;;
let lettre_of_string = function
    | "A" -> A
    | "B" -> B
    | "C" -> C
    | _ -> failwith "Lettre pas dans Sigma"
;;
let dot (nom : string) (a : afd) : unit =
    let f = open_out nom in
    let print_edge i l = try
        let e = List.assoc l a.transition.(i) in
        Printf.fprintf f "  %d -> %d [label=%s]\n"
        i e (string_of_lettre l)
    with Not_found -> ()
    in
    Printf.fprintf f "digraph g {\n";
    Printf.fprintf f "  node [shape=circle];\n";
    for i = 0 to a.taille-1 do
        print_edge i A;
        print_edge i B;
        print_edge i C
    done;
    Printf.fprintf f "}\n";
    close_out f;
;;<jupyter_output><empty_output><jupyter_text>Reconnaissance d'un motUne première approche est d'écrire une fonction récursive qui lit la première lettre du mot `m` et continue.On peut aussi écrire une fonction itérative qui boucle sur les lettres du mot `m`, et garde un `q : etat ref` pour l'état courant.On peut utiliser les fonctions `trouve` et `existe` que l'on a écrit plus haut, ou bien utiliser `List.mem_assoc` et `List.assoc` de la bibliothèque standard, comme on veut. Récursivement<jupyter_code>let lecture (a : afd) (m : mot) : bool =
    let rec lire_lettre (e : etat) (m : mot) : bool =
        match m with
        | l::u ->
            if List.mem_assoc l a.transition.(e) then
                lire_lettre (List.assoc l a.transition.(e)) u
            else false
        | [] ->
            List.mem e a.finals
    in
    lire_lettre a.initial m
;;<jupyter_output><empty_output><jupyter_text>Itérativement<jupyter_code>let lecture2 (a : afd) (m : mot) : bool =
    let q = ref (a.initial) in
    List.iter (fun l -> begin
        if List.mem_assoc l a.transition.(!q) then
            q := List.assoc l a.transition.(!q)
        end
    ) m;
    List.mem !q a.finals;
;;<jupyter_output><empty_output><jupyter_text>Deux exemples d'automates<jupyter_code>let fin_ba = {
    taille = 3;
    initial = 0;
    finals = [2];
    (*transition = [ (* si ((etat * lettre) * etat) list *)
        ((0, A), 0); ((0, B), 1); ((0, C), 0));
        ((1, A), 2); ((1, B), 1); ((1, C), 0));
        ((2, A), 0); ((2, B), 1); ((2, C), 0));
    ]*)
    (*transition = [ (* si ((etat * (lettre * etat) list) list *)
        (0, [(A, 0); (B, 1); (C, 0)]);
        (1, [(A, 2); (B, 1); (C, 0)]);
        (2, [(A, 0); (B, 1); (C, 0)]);
    ])*)
    transition = [| (* si ((lettre, etat) list) array *)
        [(A, 0); (B, 1); (C, 0)]; (* état 0 *)
        [(A, 2); (B, 1); (C, 0)]; (* état 1 *)
        [(A, 0); (B, 1); (C, 0)]; (* état 1 *)
    |]
};;
dot "afd__fin_ba.dot" fin_ba;;
Sys.command "ls -larth afd__fin_ba.dot";;
Sys.command "cat afd__fin_ba.dot";;
Sys.command "dot -Tsvg -o afd__fin_ba.svg afd__fin_ba.dot";;
Sys.command "ls -larth afd__fin_ba.svg";;<jupyter_output><empty_output><jupyter_text>![Automate Fini Déterministe - Reconnaissance des mots finissants par BA](afd__fin_ba.svg) Autre exemple :<jupyter_code>let debut_ab = {
    taille = 3;
    initial = 0;
    finals = [2];
    transition = [|
        [(A, 1)];
        [(B, 2)];
        [(A, 2); (B, 2); (C, 2)]
    |]
};;
dot "afd__debut_ab.dot" debut_ab;;
Sys.command "ls -larth afd__debut_ab.dot";;
Sys.command "cat afd__debut_ab.dot";;
Sys.command "dot -Tsvg -o afd__debut_ab.svg afd__debut_ab.dot";;
Sys.command "ls -larth afd__debut_ab.svg";;<jupyter_output><empty_output><jupyter_text>![Automate Fini Déterministe - Reconnaissance des mots commençants par AB](afd__debut_ab.svg)  Exemple de lecturesOn doit vérifier que ces deux automates reconnaissent bien respectivement les mots terminants par $ba$ et les mots commençants par $ab$.<jupyter_code>let _ = lecture  fin_ba [A;B;A];;
let _ = lecture  fin_ba [A;B;A;A];;

let _ = lecture  debut_ab [A;B;A];;
let _ = lecture  debut_ab [B;A;A];;
let _ = lecture2  fin_ba [A;B;A];;
let _ = lecture2  fin_ba [A;B;A;A];;

let _ = lecture2  debut_ab [A;B;A];;
let _ = lecture2  debut_ab [B;A;A];;<jupyter_output><empty_output><jupyter_text>Complétion (DIFFICILE)<jupyter_code>let complete (a:afd) : afd =
    let puit = a.taille in
    let ajoute_arc (l : lettre) (e : etat) (asso : (lettre, etat) assoc) =
        if List.mem_assoc l a.transition.(e)
        then asso
        else (l, puit) :: asso
    in
    let complete_etat e =
        if e < a.taille then
            ajoute_arc A e
            (ajoute_arc B e
                (ajoute_arc C e
                    a.transition.(e)
                )
            )
        else
            [(A, puit); (B, puit); (C, puit)]
    in
    {
        a with
        taille = a.taille + 1;
        transition = Array.init (a.taille + 1) complete_etat
    }
;;
let com_debut_ab = complete debut_ab;;
dot "afd__com_debut_ab.dot" com_debut_ab;;
Sys.command "ls -larth afd__com_debut_ab.dot";;
Sys.command "cat afd__com_debut_ab.dot";;
Sys.command "dot -Tsvg -o afd__com_debut_ab.svg afd__com_debut_ab.dot";;
Sys.command "ls -larth afd__com_debut_ab.svg";;<jupyter_output><empty_output><jupyter_text>![Automate Fini Déterministe - Reconnaissance des mots finissants par BA](afd__com_debut_ab.svg)  Complémentaire (plus dur)<jupyter_code>let complementaire (a : afd) : afd =
    let rec finals = function
        | n when n < 0 -> []
        | n when n != a.initial -> n :: finals (n-1)
        | n -> finals (n-1)
    in
    let a' = complete a in
    { 
        taille = a.taille +1;
        initial = a.initial;
        finals = finals (a.taille + 1);
        transition = a'.transition
    }
let not_debut_ab = complementaire debut_ab;;
dot "afd__not_debut_ab.dot" not_debut_ab;;
Sys.command "ls -larth afd__not_debut_ab.dot";;
Sys.command "cat afd__not_debut_ab.dot";;
Sys.command "dot -Tsvg -o afd__not_debut_ab.svg afd__not_debut_ab.dot";;
Sys.command "ls -larth afd__not_debut_ab.svg";;<jupyter_output><empty_output><jupyter_text>![Autom<NAME> - Reconnaissance des mots finissants par BA](afd__not_debut_ab.svg) ---- Expressions régulièresOn se fixe $\Sigma = \{a, b, c\}$.On rappelle la grammaire des expressions régulières :     ::=    | ∅    | ε    | a (lettre dans Sigma)    |  +     |  .     | *  Exercice 10 : `regexp`On représente ça le plus simplement possible, avec un type multiple :<jupyter_code>type regexp =
  | Vide
  | Epsilon (* On peut faire sans ! *)
  | Lettre of lettre
  | Somme of (regexp * regexp)
  | Concat of (regexp * regexp)
  | Etoile of regexp<jupyter_output><empty_output><jupyter_text>Exercice 11 : deux regexp pour les deux automates $A_1$, $A_2$On peut définir des valeurs intermédiaires pour écrire les exemples plus rapidement :<jupyter_code>let a = Lettre A;;
let b = Lettre B;;
let c = Lettre C;;
let sigma = Somme (Somme (a, b), c);;
let sigmaetoile = Etoile sigma;;

let la1 = Concat (sigmaetoile, Concat (a,b));;
let la2 = Concat (Concat (b, a), sigmaetoile);;<jupyter_output><empty_output><jupyter_text>Un exemple plus long sera l'expression régulière reconnaissant $\Sigma^7\Sigma^*$ les mots de longueur au moins $7$.<jupyter_code>let rec au_moins_longueur = function
    | 0 -> sigmaetoile
    | n -> Concat (sigma, au_moins_longueur (n - 1))
;;

let au_moins7 = au_moins_longueur 7;;<jupyter_output><empty_output><jupyter_text>Exercice 12 : `to_string` On peut faire une première version assez simple, qui sera assez moche puisqu'il y aura plein de parenthèses partout :<jupyter_code>let rec regexp_to_string = function
    | Vide -> "{}"
    | Epsilon -> "Epsilon"
    | Lettre A -> "A"
    | Lettre B -> "B"
    | Lettre C -> "C"
    | Somme (r1, r2) ->
        "(" ^ (regexp_to_string r1) ^ " + " ^ (regexp_to_string r2) ^ ")"
    | Concat (r1, r2) ->
        "(" ^ (regexp_to_string r1) ^ " . " ^ (regexp_to_string r2) ^ ")"
    | Etoile r -> "(" ^ (regexp_to_string r) ^ ")*"
;;
let _ = regexp_to_string la1;;
let _ = regexp_to_string la2;;
let _ = regexp_to_string au_moins7;;<jupyter_output><empty_output><jupyter_text>On peut chercher à faire un peu plus joli.L'argument `last` garde en mémoire le dernier symbole binaire ou unaire lu, `Somme`, `Concat` ou `Etoile`. Cela permet de ne pas mettre des parenthèses quand on affiche `(A+B+C)` au lieu de `(A+(B+C))` et `(A.B.C)` au lieu de `(A.(B.C))`.<jupyter_code>open Printf;;

let rec to_string last = function
    | Vide -> "{}"
    | Epsilon -> "Epsilon"
    | Lettre A -> "A"
    | Lettre B -> "B"
    | Lettre C -> "C"
    | Somme (r1, r2) ->
        if last="+" || last="*" then
            sprintf "%s + %s" (to_string "+" r1) (to_string "+" r2)
        else
            sprintf "(%s + %s)" (to_string "+" r1) (to_string "+" r2)
    | Concat (r1, r2) ->
        if last="." || last="*" then
            sprintf "%s . %s" (to_string "." r1) (to_string "." r2)
        else
            sprintf "(%s . %s)" (to_string "." r1) (to_string "." r2)
    | Etoile r -> sprintf "(%s)*" (to_string "*" r)
;;

let regexp_to_string = to_string "*";;<jupyter_output><empty_output><jupyter_text>Exemples :<jupyter_code>let _ = regexp_to_string Vide;;
let _ = regexp_to_string Epsilon;;
let _ = regexp_to_string (Etoile Epsilon);;
let _ = regexp_to_string la1;;
let _ = regexp_to_string la2;;
let _ = regexp_to_string au_moins7;;<jupyter_output><empty_output><jupyter_text>Exercice 13 : `est_vide`On teste si le langage généré par l'expression régulière est vide ou non.Une étoile n'est jamais vide, même $\varepsilon^* = \emptyset^* = \{\varepsilon\}$.<jupyter_code>let rec est_vide = function
    | Vide -> true
    | Epsilon -> false
    | Lettre _ -> false
    | Somme (r1, r2) | Concat (r1, r2) -> est_vide r1 && est_vide r2
    | Etoile _ -> false (* piège ! *)
;;
let _ = est_vide Vide;;
let _ = est_vide sigma;;
let _ = est_vide la1;;
let _ = est_vide la2;;
let _ = est_vide (Etoile Vide);;
let _ = est_vide (Etoile Epsilon);;
let _ = est_vide Epsilon;;<jupyter_output><empty_output><jupyter_text>Exercice 14 : `est_fini`Pour tester si le langage généré est fini, il faut réfléchir un peu plus, parce qu'une étoile $e^*$ est infinie à condition que le langage généré par l'expression $e$ soit non vide **et pas réduit au sigleton $\{\varepsilon\}$**!<jupyter_code>let rec est_vide_ou_epsilon = function
    | Vide -> true
    | Epsilon -> true
    | Lettre _ -> false
    | Somme (r1, r2) | Concat (r1, r2) -> est_vide_ou_epsilon r1 || est_vide_ou_epsilon r2
    | Etoile r -> est_vide_ou_epsilon r
;;
let rec est_fini = function
    | Vide -> true
    | Epsilon -> true
    | Lettre _ -> true
    | Somme (r1, r2) | Concat (r1, r2) -> est_fini r1 && est_fini r2
    | Etoile r -> est_vide_ou_epsilon r
    (* Piège car [Etoile Vide] est fini, [Etoile Epsilon] est fini aussi ! *)
;;
let _ = est_fini Vide;;
let _ = est_fini Epsilon;;
let _ = est_fini sigma;;
let _ = est_fini la1;;
let _ = est_fini la2;;
let _ = est_fini (Etoile Vide);;
let _ = est_fini (Etoile Epsilon);;
let _ = est_fini (Etoile (Somme (Epsilon, Epsilon)));;
let _ = est_fini (Etoile (Somme (Vide, Epsilon)));;
let _ = est_fini (Etoile (Somme (Vide, Vide)));;
let _ = est_fini (Etoile (Concat (Epsilon, Epsilon)));;
let _ = est_fini (Etoile (Concat (Vide, Epsilon)));;
let _ = est_fini (Etoile (Concat (Vide, Vide)));;
let _ = est_fini (Etoile sigma);;<jupyter_output><empty_output><jupyter_text>Exercice 15 : `pile_ou_face`On pense bien à initialiser le générateur de nombres pseudo aléatoires avec [`Random.self_init`](https://caml.inria.fr/pub/docs/manual-ocaml/libref/Random.htmlVALself_init).<jupyter_code>type piece = Pile | Face;;
Random.self_init ();;

let pile_ou_face () =
    match Random.int 2 with
    | 0 -> Pile
    | 1 -> Face
    | _ -> failwith "impossible"
;;<jupyter_output><empty_output><jupyter_text>Par exemple :<jupyter_code>let _ = Array.init 10 (fun _ -> pile_ou_face ());;
let _ = Array.init 10 (fun _ -> pile_ou_face ());;
let _ = Array.init 10 (fun _ -> pile_ou_face ());;<jupyter_output><empty_output><jupyter_text>Exercice 16 : `mot_aleatoire`Ce n'est pas trop compliqué : l'aléatoire est utilisé dans une somme, pour choisir l'un ou l'autre des expressions avec probabilité $1/2$, et dans une étoile.En fait, il faut faire attention avec ces deux cas, parce que si l'un des deux morceaux est vide, il faut choisir l'autre (donc `est_fini` sera utile).A noter que le choix d'implémentation de l'aléatoire dans l'étoile donne une distribution sur la longueur qui est non triviale.Un bon exercice serait de trouver la distribution de la longueur d'un mot aléatoire généré par la fonction ci-dessous à partir de l'expression régulière $a^*$. (est-ce toujours 2 ? une variable aléatoire suivant une loi de Poisson de paramètre $\lambda=1/2$ ? une loi exponentielle ?). Envoyez moi vos réponsez [par mail](http://perso.crans.org/besson/callme) (ou [ce formulaire](http://perso.crans.org/besson/contact/)).<jupyter_code>let rec mot_aleatoire = function
    | Vide -> failwith "langage vide"
    | Epsilon -> [] (* mot vide = liste de lettres vides *)
    | Lettre l -> [l]
    (* si une est vide on doit pas la choisir *)
    | Somme (r1, r2) when est_vide r1 -> mot_aleatoire r2
    | Somme (r1, r2) when est_vide r2 -> mot_aleatoire r1
    | Somme (r1, r2) -> begin
        match pile_ou_face() with
        | Pile -> mot_aleatoire r1
        | Face -> mot_aleatoire r2
    end
    | Concat (r1, r2) ->
        let m1 = mot_aleatoire r1 in
        let m2 = mot_aleatoire r2 in
        m1 @ m2
    (* Etoile (quelque chose qui est vide) devrait marcher et renvoyer vide *)
    | Etoile r when est_vide r -> [] (* mot vide *)
    | Etoile r -> begin
        match pile_ou_face() with
        | Pile -> []
        | Face -> (mot_aleatoire r) @ (mot_aleatoire (Etoile r))
    end
;;<jupyter_output><empty_output><jupyter_text>On peut faire quelques exemples :<jupyter_code>let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la1;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire la2;;
let _ = mot_aleatoire au_moins7;;
let _ = mot_aleatoire au_moins7;;
let _ = mot_aleatoire au_moins7;;
let _ = mot_aleatoire au_moins7;;
let _ = mot_aleatoire au_moins7;;
let _ = mot_aleatoire au_moins7;;
let _ = mot_aleatoire au_moins7;;<jupyter_output><empty_output><jupyter_text>Ici, on pourrait faire des expériences numériques pour afficher une distribution (empirique) sur la longueur des mots générés pour une certaine expression régulière.> Note : le mot "généré" s'applique plutôt à une grammaire, on dit généralement "reconnu" par une expression régulière et un automate. Mais cette fonction `mot_aleatoire` permet bien, elle, de générer des mots. ---- Calcul de $\Sigma^k \cap L(A)$  Exercice 17 : `produit_cartesien`C'est assez simple à faire, quand on ne s'embête pas à chercher à être très efficace (sur les concaténations).Par contre, cette implémentation est efficace sur les appels récursifs, elle utilise cette fonction interne `aux` et un accumulateur `acc`.Notez l'implémentation générique qui permet de transformer comme on veut couple d'éléments des deux listes, de type `'a` et `'b`, en un élément de type `'c`. En pratique, `fun a b -> (a, b)` sera utilisé pour faire le "vrai" produit cartésien.<jupyter_code>let produit_cartesien (prod : 'a -> 'b -> 'c) (a : 'a list) (b : 'b list) : 'c list =
    let rec aux acc a =
    match a with
    | [] -> acc
    | va :: qa -> aux ((List.map (fun vb -> prod va vb) b) @ acc) qa
    in
    List.rev (aux [] a)
;;<jupyter_output><empty_output><jupyter_text>Par exemple :<jupyter_code>produit_cartesien (fun a b -> (a, b)) [1; 2] ["ok"; "pas"; "probleme"];;<jupyter_output><empty_output><jupyter_text>Liste de tous les mots de $\Sigma^k$ On peut commencer par construire $\Sigma^k$ comme une expression régulière, c'est très simple, mais ça ne sera pas suffisant :<jupyter_code>let rec sigma_k (k : int) : regexp =
    match k with
    | n when n < 1 -> Vide
    | 1 -> sigma
    | n -> Concat (sigma, sigma_k (n - 1))
;;
regexp_to_string (sigma_k 0);;
regexp_to_string (sigma_k 1);;
regexp_to_string (sigma_k 4);;
regexp_to_string (sigma_k 12);;<jupyter_output><empty_output><jupyter_text>On a besoin de créer une liste de mots, tous les mots dans $\Sigma^k$ (il y en a exactement $|\Sigma|^k$, attention ça grandit vite !)<jupyter_code>let alphabet = [A; B; C];; (* Sigma *)

let rec tous_mots_sigma_k (alphabet : lettre list) (k : int) : mot list =
    match k with
    | k when k < 1 -> []
    | 1 -> List.map (fun lettre -> [lettre]) alphabet
    | k -> List.concat (
        List.map (
            fun lettre -> (
                List.map (fun mot -> lettre :: mot)
                (tous_mots_sigma_k alphabet (k - 1))
            )
        )
        alphabet
    )
;;
let _ = tous_mots_sigma_k alphabet 0;;
let _ = tous_mots_sigma_k alphabet 1;;
let _ = tous_mots_sigma_k alphabet 2;;
let _ = tous_mots_sigma_k alphabet 3;;<jupyter_output><empty_output><jupyter_text>Exercice 19 : `filtre`C'est très rapide, et c'est exactement la fonction `List.filter` de la bibliothèque standard. Attention, en français c'est filtre (tre) et en anglais (américain) c'est filter (ter).<jupyter_code>let rec filtre (pred : 'a -> bool) (l : 'a list) : 'a list =
    match l with
    | [] -> []
    | h :: q when pred h -> h :: (filtre pred q)
    | _ :: q -> filtre pred q
;;
List.filter;;
filtre (fun x -> x mod 2 = 0) [1; 2; 3; 4];;
List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4];;<jupyter_output><empty_output><jupyter_text>Exercice 20C'est très facile ! Il suffit d'utiliser la fonction `lecture` comme un prédicat binaire :<jupyter_code>lecture;;
let sigmak_inter_LA (k : int) (a : afd) : mot list =
    let s_k = tous_mots_sigma_k alphabet k in
    filtre (fun mot -> lecture a mot) s_k
;;<jupyter_output><empty_output><jupyter_text>Exemples pour les deux automates du début tels que $L(A)$ soient $\Sigma^* b a$ et $a b \Sigma^*$.Il y a $|\Sigma|^2 = 3^2 = 9$ mots dans les deux cas, puisque $2$ lettres parmi les $4$ (pour des mots de $\Sigma^4$) sont déjà fixées.<jupyter_code>let _ = sigmak_inter_LA 4 fin_ba;;

let _ = sigmak_inter_LA 4 debut_ab;;<jupyter_output><empty_output><jupyter_text>Automate produit (PLUS DUR)C'est plus dur mais assez guidé.  Exercice 21 : `bijection`<jupyter_code>type f_intint_int = (int * int -> int);;
type f_int_intint = (int -> int * int);;
let bijection (p : int) (q : int) : f_intint_int * f_int_intint =
    let f (n, m) = m + n * q in
    let finv x =
        let m = x mod q and n = x / q in
        assert ((f (n, m)) = x);
        (n, m);
    in
    f, finv
;;<jupyter_output>File "[9]", line 1, characters 15-16:
Warning 27: unused variable p.<jupyter_text>Il faut absolument la tester, au moins vérifier que $f^{-1}(f(n, m)) = (n, m)$ et $f(f^{-1}(x)) = x$ pour tout $n,m \in [0,p-1] \times [0,q-1]$ et $x \in [0, pq-1]$.<jupyter_code>let p = 2 and q = 4;;
let f, finv = bijection 2 4;;

for n = 0 to p - 1 do
    flush_all();
    for m = 0 to q - 1 do
        Printf.printf "\n%i, %i -> %i" n m (f (n, m)); 
        assert ((n, m) = finv (f (n, m)));
    done;
    flush_all();
done;;

for x = 0 to p*q - 1 do
    flush_all();
    let n, m = finv x in
    Printf.printf "\n%i -> %i, %i" x n m ; 
    assert (x = f (finv x));
done;;<jupyter_output><empty_output><jupyter_text>Exercice 22 On utilise `produit_cartesien` pour les états finaux, une simple paire pour l'état initial, et un peu de calcul pour les transitions.L'idée est d'utiliser cette bijection $f$ pour coder les paires comme des entiers simples (et donc produire un automate représenté par un `afd`).<jupyter_code>let alphabet = [A; B; C];;

let automate_produit (a1 : afd) (a2 : afd) =
    let p, i1, f1, d1 = a1.taille, a1.initial, a1.finals, a1.transition in
    let q, i2, f2, d2 = a2.taille, a2.initial, a2.finals, a2.transition in
    (* les bijections *)
    let taille = p * q in
    let f, finv = bijection p q in
    (* état initial *)
    let initial = f (i1, i2) in
    (* peut contenir des doublons, pas grave *)
    let finals = List.map f (produit_cartesien (fun x y -> (x, y)) f1 f2) in
    (* et moins trivial pour les transitions *)
    let transition = Array.init taille (fun ij -> (* pour l'état (i, j) *)
        let i, j = finv ij in
        (* d1.(i) est une liste de (lettre, etat) = (a, q1) pour i --a-> q1 *)
        let transition_i_1 = d1.(i) in
        (* d2.(j) est une liste de (lettre, etat) = (b, q2) pour j --b-> q2 *)
        let transition_j_2 = d2.(j) in
        (* on doit trouver les transitions avec la meme lettre et produire i --a-> f q1 q2 *)
        List.concat (
            List.map (fun lettre ->
                (* pour cette lettre on cherche la transition jointe qui convient, si elle existe *)
                if (List.mem_assoc lettre transition_i_1) && (List.mem_assoc lettre transition_j_2) then
                begin
                    let q1 = List.assoc lettre transition_i_1 in
                    let q2 = List.assoc lettre transition_j_2 in
                    [(lettre, f(q1, q2))]
                end else []
            )
        alphabet)
    ) in
    { taille; initial; finals; transition }
;;<jupyter_output><empty_output><jupyter_text>Exemple :<jupyter_code>debut_ab;;
fin_ba;;
let test_produit = automate_produit debut_ab fin_ba;;
dot "afd__test_produit.dot" test_produit;;
Sys.command "ls -larth afd__test_produit.dot";;
Sys.command "cat afd__test_produit.dot";;
Sys.command "dot -Tsvg -o afd__test_produit.svg afd__test_produit.dot";;
Sys.command "ls -larth afd__test_produit.svg";;<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13938176910162295, 'fraction_numerical': 0.015208875135793528, 'mean_word_length': 3.4891384660854143, 'pattern_counts': {'":': 5, '<': 183, '<?xml version=': 0, '>': 308, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '44', 'dir': 'jupyter-structured-clean-dedup', 'id': '605541', 'license': 'MIT', 'n_tokens_mistral': 11989, 'n_tokens_neox': 11712, 'n_words': 3378, 'path': 'agreg/TP_Programmation_2017-18/TP4__OCaml.ipynb', 'repo_name': 'doc22940/notebooks-2', 'size': '30401'}