{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  TP 4 - Programmation pour la préparation à l'agrégation maths option info
2  Remise en forme : listes associatives
2.1  Exercice 1 : appartient
2.2  Exercice 2 : insere
2.3  Exercice 3 : existe
2.4  Exercice 4 : trouve
2.5  Exercice 5 : supprime
2.6  Question bonus : avec des tables d'associations
3  Automates finis déterministes
3.1  Types de données
3.2  Affichage (PAS DANS LE TP)
3.3  Reconnaissance d'un mot
3.3.1  Récursivement
3.3.2  Itérativement
3.4  Deux exemples d'automates
3.5  Exemple de lectures
3.6  Complétion (DIFFICILE)
3.7  Complémentaire (plus dur)
4  Expressions régulières
4.1  Exercice 10 : regexp
4.2  Exercice 11 : deux regexp pour les deux automates A1\" role=\"presentation\" style=\"position: relative;\">𝐴1A1, A2\" role=\"presentation\" style=\"position: relative;\">𝐴2A2
4.3  Exercice 12 : to_string
4.4  Exercice 13 : est_vide
4.5  Exercice 14 : est_fini
4.6  Exercice 15 : pile_ou_face
4.7  Exercice 16 : mot_aleatoire
5  Calcul de Σ𝑘∩𝐿(𝐴)
5.1  Exercice 17 : produit_cartesien
5.2  Liste de tous les mots de Σ𝑘
5.3  Exercice 19 : filtre
5.4  Exercice 20
6  Automate produit (PLUS DUR)
6.1  Exercice 21 : bijection
6.2  Exercice 22
7  Conclusion
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# TP 4 - Programmation pour la préparation à l'agrégation maths option info\n", "TP 4 : Automates et langages réguliers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- En OCaml." ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val print : ('a, out_channel, unit) format -> 'a = \n" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "The OCaml toplevel, version 4.04.2\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let print = Printf.printf;;\n", "Sys.command \"ocaml -version\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "# Remise en forme : listes associatives\n", "\n", "Certaines de ces fonctions sont dans la bibliothèque standard dans le module `List`, avec des fonctions contenant `assoc` dans leur nom :" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : 'a -> 'a list -> bool = \n" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.mem;; (* appartient *)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : 'a -> ('a * 'b) list -> 'b = \n" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.assoc;; (* trouve *)" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : 'a -> ('a * 'b) list -> bool = \n" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.mem_assoc;; (* existe *)" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : 'a -> ('a * 'b) list -> ('a * 'b) list = \n" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.remove_assoc;; (* supprime *)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 1 : `appartient`\n", "\n", "On propose plusieurs implémentations, toutes similaires mais de complexités différentes.\n", "Je vous laisse trouver les différences de comportement (lesquelles sont tout le temps linéaire, au mieux $\\mathcal{O}(1)$ etc)." ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val appartient : 'a -> 'a list -> bool = \n" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(* En O(n) pour une liste de taille n (pire cas), en O(1) meilleur cas. *)\n", "let rec appartient (x:'a) (l:'a list) : bool =\n", " match l with\n", " | [] -> false\n", " | y :: _ when x = y -> true\n", " | _ :: q -> appartient x q\n", ";;" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val liste1 : int list = [1; 2; 3]\n" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val couple1 : int * int * int = (1, 2, 3)\n" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let liste1 = [ 1; 2; 3 ];;\n", "let couple1 = (1, 2, 3) ;;" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val appartient : 'a -> 'a list -> bool = \n" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(* En O(n) pour une liste de taille n (pire cas), en O(1) meilleur cas. *)\n", "let rec appartient (x:'a) (l:'a list) : bool =\n", " match l with\n", " | [] -> false\n", " | y :: q -> (x = y) || appartient x q\n", ";;" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val appartient : 'a -> 'a list -> bool = \n" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(* En O(n) pour une liste de taille n (pire cas), en O(n) meilleur cas. *)\n", "let rec appartient (x:'a) (l:'a list) : bool =\n", " match l with\n", " | [] -> false\n", " | y :: q -> appartient x q || x = y\n", ";;" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val appartient : 'a -> 'a list -> bool = \n" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let appartient = List.mem;;" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assert (appartient 3 [1;2;3;4;5]) ;;\n", "assert (not (appartient 9 [1;2;3;4;5])) ;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 2 : `insere`\n", "\n", "On a envie d'écrire rapidement cela :" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val insere : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list = \n" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let insere (k:'a) (v:'b) (l: ('a*'b) list) : ('a*'b) list =\n", " (k,v) :: l\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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` ?\n", "Vous pouvez essayer d'implémenter chacun des variantes !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On construit un exemple de petite liste associative :" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val justiceleague : (string * string) list =\n", " [(\"Superman\", \"Clark Kent\"); (\"Batman\", \"Bruce Wayne\")]\n" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let justiceleague = insere \"Superman\" \"Clark Kent\" (insere \"Batman\" \"Bruce Wayne\" []);;" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val communaute : (string * string) list =\n", " [(\"Aragorn\", \"rodeur\"); (\"Gandalf\", \"magicien\"); (\"Gimli\", \"nain\");\n", " (\"Legolas\", \"elfe\"); (\"Frodon\", \"hobbit\")]\n" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let communaute =\n", " insere \"Aragorn\" \"rodeur\" (\n", " insere \"Gandalf\" \"magicien\" (\n", " insere \"Gimli\" \"nain\" (\n", " insere \"Legolas\" \"elfe\" (\n", " insere \"Frodon\" \"hobbit\"\n", " []\n", " )\n", " )\n", " )\n", " )\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> La syntaxe est lourde, en comparaison d'un dictionnaire simple comme en Python...\n", "> ```python\n", "> communaute = { \"Aragorn\": \"rodeur\", \"Gandalf\": \"magicien\", \"Gimli\": \"nain\", \"Legolas\": \"elfe\", \"Frodon\": \"hobbit\" }\n", "> ```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 3 : `existe`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Première version, \"à la main\" :" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val existe : 'a -> ('a * 'b) list -> bool = \n" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec existe (cle : 'a) (l : ('a * 'b) list) : bool =\n", " match l with\n", " | [] -> false\n", " | (k, _) :: _ when cle = k -> true\n", " | _ :: q -> existe cle q\n", ";;" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assert (existe \"Frodon\" communaute) ;;\n", "assert (not (existe \"Boromir\" communaute));;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En utilisant la bibliothèque standard :" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "val existe : 'a -> ('a * 'b) list -> bool = \n" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let existe (cle : 'a) (l : ('a * 'b) list) : bool =\n", " List.exists (fun (k, _) -> cle = k) l\n", ";;" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assert (existe \"Frodon\" communaute) ;;\n", "assert (not (existe \"Boromir\" communaute));;" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val existe : 'a -> ('a * 'b) list -> bool = \n" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let existe = List.mem_assoc;;" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assert (existe \"Frodon\" communaute) ;;\n", "assert (not (existe \"Boromir\" communaute));;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 4 : `trouve`\n", "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` :" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "ename": "error", "evalue": "runtime_error", "output_type": "error", "traceback": [ "\u001b[31mException: Not_found.\nRaised at file \"list.ml\", line 158, characters 16-25\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m" ] } ], "source": [ "List.assoc \"ok\" [];;" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val trouve : 'a -> ('a * 'b) list -> 'b = \n" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec trouve (cle : 'a) (l : ('a * 'b) list) : 'b =\n", " match l with\n", " | [] -> raise Not_found\n", " | (k, v) :: _ when cle = k -> v\n", " | _ :: q -> trouve cle q\n", ";;" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assert ((trouve \"Gandalf\" communaute) = \"magicien\");;\n", "assert (try (trouve \"Boromir\" communaute) = \"guerrier\" with Not_found -> true);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec la bibliothèque standard :" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val trouve : 'a -> ('a * 'b) list -> 'b = \n" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let trouve = List.assoc;;" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "assert ((trouve \"Gandalf\" communaute) = \"magicien\");;\n", "assert (try (trouve \"Boromir\" communaute) = \"guerrier\" with Not_found -> true);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 5 : `supprime`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On choisit la sémantique suivante : l'exception `Not_found` est levée si la clé n'est pas présente.\n", "On supprime sinon la *première* occurrence de la clé (rappel : `insere` ajoute `(cle, valeur)` même si `cle` est déjà présente)." ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val supprime : 'a -> ('a * 'b) list -> ('a * 'b) list = \n" ] }, "execution_count": 57, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec supprime (cle : 'a) (l : ('a*'b) list) : ('a*'b) list =\n", " match l with\n", " | [] -> raise Not_found\n", " | (k, _) :: q when cle = k -> q\n", " | p :: q -> p :: supprime cle q\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple :" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : (string * string) list =\n", "[(\"Aragorn\", \"rodeur\"); (\"Gandalf\", \"magicien\"); (\"Gimli\", \"nain\");\n", " (\"Legolas\", \"elfe\"); (\"Frodon\", \"hobbit\")]\n" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "communaute;;" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "ename": "error", "evalue": "runtime_error", "output_type": "error", "traceback": [ "\u001b[31mException: Not_found.\nRaised at file \"[57]\", line 3, characters 18-27\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m" ] } ], "source": [ "supprime \"Gandalf\" [ ];;" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val fin_film_1 : (string * string) list =\n", " [(\"Aragorn\", \"rodeur\"); (\"Gimli\", \"nain\"); (\"Legolas\", \"elfe\");\n", " (\"Frodon\", \"hobbit\")]\n" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let fin_film_1 = supprime \"Gandalf\" communaute;;" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val dans100ans : (string * string) list =\n", " [(\"Aragorn\", \"rodeur\"); (\"Gandalf\", \"magicien\"); (\"Gimli\", \"nain\");\n", " (\"Legolas\", \"elfe\")]\n" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let dans100ans = supprime \"Frodon\" communaute;;" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val debut_film_3 : (string * string) list =\n", " [(\"Gandalf\", \"magicien blanc\"); (\"Aragorn\", \"rodeur\"); (\"Gimli\", \"nain\");\n", " (\"Legolas\", \"elfe\"); (\"Frodon\", \"hobbit\")]\n" ] }, "execution_count": 62, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let debut_film_3 = insere \"Gandalf\" \"magicien blanc\" fin_film_1;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Question bonus : avec des tables d'associations\n", "La bibliothèque standard fournit le module [`Map`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.html#VALMake).\n", "Il faut au préalable créer le bon module (syntaxe un peu difficile, avec un *foncteur*)." ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "module M :\n", " sig\n", " type key = int\n", " type +'a t\n", " val empty : 'a t\n", " val is_empty : 'a t -> bool\n", " val mem : key -> 'a t -> bool\n", " val add : key -> 'a -> 'a t -> 'a t\n", " val singleton : key -> 'a -> 'a t\n", " val remove : key -> 'a t -> 'a t\n", " val merge :\n", " (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t\n", " val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t\n", " val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int\n", " val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool\n", " val iter : (key -> 'a -> unit) -> 'a t -> unit\n", " val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b\n", " val for_all : (key -> 'a -> bool) -> 'a t -> bool\n", " val exists : (key -> 'a -> bool) -> 'a t -> bool\n", " val filter : (key -> 'a -> bool) -> 'a t -> 'a t\n", " val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t\n", " val cardinal : 'a t -> int\n", " val bindings : 'a t -> (key * 'a) list\n", " val min_binding : 'a t -> key * 'a\n", " val max_binding : 'a t -> key * 'a\n", " val choose : 'a t -> key * 'a\n", " val split : key -> 'a t -> 'a t * 'a option * 'a t\n", " val find : key -> 'a t -> 'a\n", " val map : ('a -> 'b) -> 'a t -> 'b t\n", " val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t\n", " end\n" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val t : string M.t = \n" ] }, "execution_count": 63, "metadata": {}, "output_type": "execute_result" } ], "source": [ "module M = Map.Make ( struct\n", " type t = int\n", " let compare = compare\n", " end);;\n", "\n", "let t : string M.t = (M.add 1 \"1\" (M.add 2 \"2\" (M.add 3 \"3\" M.empty)));;" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string = \"1\"\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string = \"2\"\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "ename": "error", "evalue": "runtime_error", "output_type": "error", "traceback": [ "\u001b[31mException: Not_found.\nRaised at file \"map.ml\", line 122, characters 16-25\nCalled from file \"toplevel/toploop.ml\", line 180, characters 17-56\n\u001b[0m" ] } ], "source": [ "let _ = M.mem 1 t;;\n", "let _ = M.mem 2 t;;\n", "let _ = M.mem 4 t;;\n", "\n", "let _ = M.find 1 t;;\n", "let _ = M.find 2 t;;\n", "let _ = M.find 4 t;;\n", "\n", "let _ = M.remove 1 t;;\n", "let _ = M.remove 2 t;;\n", "let _ = M.remove 4 t;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "# Automates finis déterministes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Types de données\n", "Les 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." ] }, { "cell_type": "code", "execution_count": 65, "metadata": { "code_folding": [] }, "outputs": [ { "data": { "text/plain": [ "type ('a, 'b) assoc = ('a * 'b) list\n" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type lettre = A | B | C\n" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type mot = lettre list\n" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type langage = mot list\n" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type etat = int\n" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type ('a, 'b) assoc = ('a * 'b) list;;\n", "type lettre = A | B | C;;\n", "\n", "type mot = lettre list;; (* [lettre array] marche aussi bien ! *)\n", "type langage = mot list;;\n", "type etat = int;;" ] }, { "cell_type": "code", "execution_count": 66, "metadata": { "code_folding": [] }, "outputs": [ { "data": { "text/plain": [ "type afd = {\n", " taille : int;\n", " initial : etat;\n", " finals : etat list;\n", " transition : (lettre, etat) assoc array;\n", "}\n" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(* Automate fini déterministe *)\n", "type afd = {\n", " taille : int;\n", " initial : etat;\n", " finals : etat list;\n", " (* on peut aussi utiliser : *)\n", " (* transition : (etat, (lettre, etat) assoc) assoc; *) (* comme une fonction q -> a -> q' *)\n", " (* transition : ((etat, lettre), etat) assoc; *) (* comme une fonction (q, a) -> q' *)\n", " transition : (lettre, etat) assoc array\n", "};;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Affichage (PAS DANS LE TP)\n", "On va utiliser le [langage dot](https://graphviz.readthedocs.io/en/stable/manual.html#using-raw-dot) pour afficher facilement des graphes, et donc ici, des automates.\n", "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)." ] }, { "cell_type": "code", "execution_count": 67, "metadata": { "scrolled": true }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "File \"[67]\", line 2, characters 6-7:\n", "Warning 41: A belongs to several types: lettre lettre\n", "The first one was selected. Please disambiguate if this is wrong.\n" ] }, { "data": { "text/plain": [ "val string_of_lettre : lettre -> string = \n" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let string_of_lettre = function\n", " | A -> \"A\"\n", " | B -> \"B\"\n", " | C -> \"C\"\n", ";;" ] }, { "cell_type": "code", "execution_count": 68, "metadata": { "scrolled": true }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "File \"[68]\", line 2, characters 13-14:\n", "Warning 41: A belongs to several types: lettre lettre\n", "The first one was selected. Please disambiguate if this is wrong.\n" ] }, { "data": { "text/plain": [ "val lettre_of_string : string -> lettre = \n" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let lettre_of_string = function\n", " | \"A\" -> A\n", " | \"B\" -> B\n", " | \"C\" -> C\n", " | _ -> failwith \"Lettre pas dans Sigma\"\n", ";;" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val dot : string -> afd -> unit = \n" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let dot (nom : string) (a : afd) : unit =\n", " let f = open_out nom in\n", " let print_edge i l = try\n", " let e = List.assoc l a.transition.(i) in\n", " Printf.fprintf f \" %d -> %d [label=%s]\\n\"\n", " i e (string_of_lettre l)\n", " with Not_found -> ()\n", " in\n", " Printf.fprintf f \"digraph g {\\n\";\n", " Printf.fprintf f \" node [shape=circle];\\n\";\n", " for i = 0 to a.taille-1 do\n", " print_edge i A;\n", " print_edge i B;\n", " print_edge i C\n", " done;\n", " Printf.fprintf f \"}\\n\";\n", " close_out f;\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Reconnaissance d'un mot\n", "\n", "Une première approche est d'écrire une fonction récursive qui lit la première lettre du mot `m` et continue.\n", "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.\n", "\n", "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.\n", "\n", "### Récursivement" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val lecture : afd -> mot -> bool = \n" ] }, "execution_count": 70, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let lecture (a : afd) (m : mot) : bool =\n", " let rec lire_lettre (e : etat) (m : mot) : bool =\n", " match m with\n", " | l::u ->\n", " if List.mem_assoc l a.transition.(e) then\n", " lire_lettre (List.assoc l a.transition.(e)) u\n", " else false\n", " | [] ->\n", " List.mem e a.finals\n", " in\n", " lire_lettre a.initial m\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Itérativement" ] }, { "cell_type": "code", "execution_count": 74, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val lecture2 : afd -> mot -> bool = \n" ] }, "execution_count": 74, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let lecture2 (a : afd) (m : mot) : bool =\n", " let q = ref (a.initial) in\n", " List.iter (fun l -> begin\n", " if List.mem_assoc l a.transition.(!q) then\n", " q := List.assoc l a.transition.(!q)\n", " end\n", " ) m;\n", " List.mem !q a.finals;\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Deux exemples d'automates" ] }, { "cell_type": "code", "execution_count": 75, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val fin_ba : afd =\n", " {taille = 3; initial = 0; finals = [2];\n", " transition =\n", " [|[(A, 0); (B, 1); (C, 0)]; [(A, 2); (B, 1); (C, 0)];\n", " [(A, 0); (B, 1); (C, 0)]|]}\n" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let fin_ba = {\n", " taille = 3;\n", " initial = 0;\n", " finals = [2];\n", " (*transition = [ (* si ((etat * lettre) * etat) list *)\n", " ((0, A), 0); ((0, B), 1); ((0, C), 0));\n", " ((1, A), 2); ((1, B), 1); ((1, C), 0));\n", " ((2, A), 0); ((2, B), 1); ((2, C), 0));\n", " ]*)\n", " (*transition = [ (* si ((etat * (lettre * etat) list) list *)\n", " (0, [(A, 0); (B, 1); (C, 0)]);\n", " (1, [(A, 2); (B, 1); (C, 0)]);\n", " (2, [(A, 0); (B, 1); (C, 0)]);\n", " ])*)\n", " transition = [| (* si ((lettre, etat) list) array *)\n", " [(A, 0); (B, 1); (C, 0)]; (* état 0 *)\n", " [(A, 2); (B, 1); (C, 0)]; (* état 1 *)\n", " [(A, 0); (B, 1); (C, 0)]; (* état 1 *)\n", " |]\n", "};;" ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-r--r-- 1 lilian lilian 208 nov. 27 15:08 afd__fin_ba.dot\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "digraph g {\n", " node [shape=circle];\n", " 0 -> 0 [label=A]\n", " 0 -> 1 [label=B]\n", " 0 -> 0 [label=C]\n", " 1 -> 2 [label=A]\n", " 1 -> 1 [label=B]\n", " 1 -> 0 [label=C]\n", " 2 -> 0 [label=A]\n", " 2 -> 1 [label=B]\n", " 2 -> 0 [label=C]\n", "}\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dot \"afd__fin_ba.dot\" fin_ba;;\n", "Sys.command \"ls -larth afd__fin_ba.dot\";;\n", "Sys.command \"cat afd__fin_ba.dot\";;" ] }, { "cell_type": "code", "execution_count": 77, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-r--r-- 1 lilian lilian 5,5K nov. 27 15:08 afd__fin_ba.svg\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"dot -Tsvg -o afd__fin_ba.svg afd__fin_ba.dot\";;\n", "Sys.command \"ls -larth afd__fin_ba.svg\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Automate Fini Déterministe - Reconnaissance des mots finissants par BA](afd__fin_ba.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Autre exemple :" ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val debut_ab : afd =\n", " {taille = 3; initial = 0; finals = [2];\n", " transition = [|[(A, 1)]; [(B, 2)]; [(A, 2); (B, 2); (C, 2)]|]}\n" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let debut_ab = {\n", " taille = 3;\n", " initial = 0;\n", " finals = [2];\n", " transition = [|\n", " [(A, 1)];\n", " [(B, 2)];\n", " [(A, 2); (B, 2); (C, 2)]\n", " |]\n", "};;" ] }, { "cell_type": "code", "execution_count": 79, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-r--r-- 1 lilian lilian 132 nov. 27 15:08 afd__debut_ab.dot\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "digraph g {\n", " node [shape=circle];\n", " 0 -> 1 [label=A]\n", " 1 -> 2 [label=B]\n", " 2 -> 2 [label=A]\n", " 2 -> 2 [label=B]\n", " 2 -> 2 [label=C]\n", "}\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dot \"afd__debut_ab.dot\" debut_ab;;\n", "Sys.command \"ls -larth afd__debut_ab.dot\";;\n", "Sys.command \"cat afd__debut_ab.dot\";;" ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-rw-r-- 1 lilian lilian 3,5K nov. 27 15:08 afd__debut_ab.svg\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"dot -Tsvg -o afd__debut_ab.svg afd__debut_ab.dot\";;\n", "Sys.command \"ls -larth afd__debut_ab.svg\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Automate Fini Déterministe - Reconnaissance des mots commençants par AB](afd__debut_ab.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exemple de lectures\n", "On doit vérifier que ces deux automates reconnaissent bien respectivement les mots terminants par $ba$ et les mots commençants par $ab$." ] }, { "cell_type": "code", "execution_count": 81, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = lecture fin_ba [A;B;A];;\n", "let _ = lecture fin_ba [A;B;A;A];;\n", "\n", "let _ = lecture debut_ab [A;B;A];;\n", "let _ = lecture debut_ab [B;A;A];;" ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = lecture2 fin_ba [A;B;A];;\n", "let _ = lecture2 fin_ba [A;B;A;A];;\n", "\n", "let _ = lecture2 debut_ab [A;B;A];;\n", "let _ = lecture2 debut_ab [B;A;A];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Complétion (DIFFICILE)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val complete : afd -> afd = \n" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let complete (a:afd) : afd =\n", " let puit = a.taille in\n", " let ajoute_arc (l : lettre) (e : etat) (asso : (lettre, etat) assoc) =\n", " if List.mem_assoc l a.transition.(e)\n", " then asso\n", " else (l, puit) :: asso\n", " in\n", " let complete_etat e =\n", " if e < a.taille then\n", " ajoute_arc A e\n", " (ajoute_arc B e\n", " (ajoute_arc C e\n", " a.transition.(e)\n", " )\n", " )\n", " else\n", " [(A, puit); (B, puit); (C, puit)]\n", " in\n", " {\n", " a with\n", " taille = a.taille + 1;\n", " transition = Array.init (a.taille + 1) complete_etat\n", " }\n", ";;" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val com_debut_ab : afd =\n", " {taille = 4; initial = 0; finals = [2];\n", " transition =\n", " [|[(B, 3); (C, 3); (A, 1)]; [(A, 3); (C, 3); (B, 2)];\n", " [(A, 2); (B, 2); (C, 2)]; [(A, 3); (B, 3); (C, 3)]|]}\n" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let com_debut_ab = complete debut_ab;;" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-rw-r-- 1 lilian lilian 265 oct. 10 17:23 afd__com_debut_ab.dot\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "digraph g {\n", " node [shape=circle];\n", " 0 -> 1 [label=A]\n", " 0 -> 3 [label=B]\n", " 0 -> 3 [label=C]\n", " 1 -> 3 [label=A]\n", " 1 -> 2 [label=B]\n", " 1 -> 3 [label=C]\n", " 2 -> 2 [label=A]\n", " 2 -> 2 [label=B]\n", " 2 -> 2 [label=C]\n", " 3 -> 3 [label=A]\n", " 3 -> 3 [label=B]\n", " 3 -> 3 [label=C]\n", "}\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dot \"afd__com_debut_ab.dot\" com_debut_ab;;\n", "Sys.command \"ls -larth afd__com_debut_ab.dot\";;\n", "Sys.command \"cat afd__com_debut_ab.dot\";;" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-rw-r-- 1 lilian lilian 6,6K oct. 10 17:23 afd__com_debut_ab.svg\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"dot -Tsvg -o afd__com_debut_ab.svg afd__com_debut_ab.dot\";;\n", "Sys.command \"ls -larth afd__com_debut_ab.svg\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Automate Fini Déterministe - Reconnaissance des mots finissants par BA](afd__com_debut_ab.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Complémentaire (plus dur)" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val complementaire : afd -> afd = \n" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let complementaire (a : afd) : afd =\n", " let rec finals = function\n", " | n when n < 0 -> []\n", " | n when n != a.initial -> n :: finals (n-1)\n", " | n -> finals (n-1)\n", " in\n", " let a' = complete a in\n", " { \n", " taille = a.taille +1;\n", " initial = a.initial;\n", " finals = finals (a.taille + 1);\n", " transition = a'.transition\n", " }" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val not_debut_ab : afd =\n", " {taille = 4; initial = 0; finals = [4; 3; 2; 1];\n", " transition =\n", " [|[(B, 3); (C, 3); (A, 1)]; [(A, 3); (C, 3); (B, 2)];\n", " [(A, 2); (B, 2); (C, 2)]; [(A, 3); (B, 3); (C, 3)]|]}\n" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let not_debut_ab = complementaire debut_ab;;" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-rw-r-- 1 lilian lilian 265 oct. 10 17:39 afd__not_debut_ab.dot\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "digraph g {\n", " node [shape=circle];\n", " 0 -> 1 [label=A]\n", " 0 -> 3 [label=B]\n", " 0 -> 3 [label=C]\n", " 1 -> 3 [label=A]\n", " 1 -> 2 [label=B]\n", " 1 -> 3 [label=C]\n", " 2 -> 2 [label=A]\n", " 2 -> 2 [label=B]\n", " 2 -> 2 [label=C]\n", " 3 -> 3 [label=A]\n", " 3 -> 3 [label=B]\n", " 3 -> 3 [label=C]\n", "}\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 55, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dot \"afd__not_debut_ab.dot\" not_debut_ab;;\n", "Sys.command \"ls -larth afd__not_debut_ab.dot\";;\n", "Sys.command \"cat afd__not_debut_ab.dot\";;" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-rw-r-- 1 lilian lilian 6,6K oct. 10 17:43 afd__not_debut_ab.svg\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"dot -Tsvg -o afd__not_debut_ab.svg afd__not_debut_ab.dot\";;\n", "Sys.command \"ls -larth afd__not_debut_ab.svg\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Automate Fini Déterministe - Reconnaissance des mots finissants par BA](afd__not_debut_ab.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "# Expressions régulières\n", "\n", "On se fixe $\\Sigma = \\{a, b, c\\}$.\n", "\n", "On rappelle la grammaire des expressions régulières :\n", "\n", " ::=\n", " | ∅\n", " | ε\n", " | a (lettre dans Sigma)\n", " | + \n", " | . \n", " | *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 10 : `regexp`\n", "\n", "On représente ça le plus simplement possible, avec un type multiple :" ] }, { "cell_type": "code", "execution_count": 84, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type regexp =\n", " Vide\n", " | Epsilon\n", " | Lettre of lettre\n", " | Somme of (regexp * regexp)\n", " | Concat of (regexp * regexp)\n", " | Etoile of regexp\n" ] }, "execution_count": 84, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type regexp =\n", " | Vide\n", " | Epsilon (* On peut faire sans ! *)\n", " | Lettre of lettre\n", " | Somme of (regexp * regexp)\n", " | Concat of (regexp * regexp)\n", " | Etoile of regexp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 11 : deux regexp pour les deux automates $A_1$, $A_2$\n", "\n", "On peut définir des valeurs intermédiaires pour écrire les exemples plus rapidement :" ] }, { "cell_type": "code", "execution_count": 85, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val a : regexp = Lettre A\n" ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val b : regexp = Lettre B\n" ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val c : regexp = Lettre C\n" ] }, "execution_count": 85, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let a = Lettre A;;\n", "let b = Lettre B;;\n", "let c = Lettre C;;" ] }, { "cell_type": "code", "execution_count": 86, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sigma : regexp = Somme (Somme (Lettre A, Lettre B), Lettre C)\n" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val sigmaetoile : regexp =\n", " Etoile (Somme (Somme (Lettre A, Lettre B), Lettre C))\n" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val la1 : regexp =\n", " Concat\n", " (Etoile (Somme (Somme (Lettre A, Lettre B), Lettre C)),\n", " Concat (Lettre A, Lettre B))\n" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val la2 : regexp =\n", " Concat\n", " (Concat (Lettre B, Lettre A),\n", " Etoile (Somme (Somme (Lettre A, Lettre B), Lettre C)))\n" ] }, "execution_count": 86, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sigma = Somme (Somme (a, b), c);;\n", "let sigmaetoile = Etoile sigma;;\n", "\n", "let la1 = Concat (sigmaetoile, Concat (a,b));;\n", "let la2 = Concat (Concat (b, a), sigmaetoile);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Un exemple plus long sera l'expression régulière reconnaissant $\\Sigma^7\\Sigma^*$ les mots de longueur au moins $7$." ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val au_moins_longueur : int -> regexp = \n" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val au_moins7 : regexp =\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Concat\n", " (Somme (Somme (Lettre A, Lettre B), Lettre C),\n", " Etoile (Somme (Somme (Lettre A, Lettre B), Lettre C)))))))))\n" ] }, "execution_count": 88, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec au_moins_longueur = function\n", " | 0 -> sigmaetoile\n", " | n -> Concat (sigma, au_moins_longueur (n - 1))\n", ";;\n", "\n", "let au_moins7 = au_moins_longueur 7;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 12 : `to_string`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut faire une première version assez simple, qui sera assez moche puisqu'il y aura plein de parenthèses partout :" ] }, { "cell_type": "code", "execution_count": 89, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "val regexp_to_string : regexp -> string = \n" ] }, "execution_count": 89, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec regexp_to_string = function\n", " | Vide -> \"{}\"\n", " | Epsilon -> \"Epsilon\"\n", " | Lettre A -> \"A\"\n", " | Lettre B -> \"B\"\n", " | Lettre C -> \"C\"\n", " | Somme (r1, r2) ->\n", " \"(\" ^ (regexp_to_string r1) ^ \" + \" ^ (regexp_to_string r2) ^ \")\"\n", " | Concat (r1, r2) ->\n", " \"(\" ^ (regexp_to_string r1) ^ \" . \" ^ (regexp_to_string r2) ^ \")\"\n", " | Etoile r -> \"(\" ^ (regexp_to_string r) ^ \")*\"\n", ";;" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : string = \"((((A + B) + C))* . (A . B))\"\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string = \"((B . A) . (((A + B) + C))*)\"\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string =\n", "\"(((A + B) + C) . (((A + B) + C) . (((A + B) + C) . (((A + B) + C) . (((A + B) + C) . (((A + B) + C) . (((A + B) + C) . (((A + B) + C))*)))))))\"\n" ] }, "execution_count": 64, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = regexp_to_string la1;;\n", "let _ = regexp_to_string la2;;\n", "let _ = regexp_to_string au_moins7;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut chercher à faire un peu plus joli.\n", "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))`." ] }, { "cell_type": "code", "execution_count": 90, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/plain": [ "val to_string : string -> regexp -> string = \n" ] }, "execution_count": 90, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val regexp_to_string : regexp -> string = \n" ] }, "execution_count": 90, "metadata": {}, "output_type": "execute_result" } ], "source": [ "open Printf;;\n", "\n", "let rec to_string last = function\n", " | Vide -> \"{}\"\n", " | Epsilon -> \"Epsilon\"\n", " | Lettre A -> \"A\"\n", " | Lettre B -> \"B\"\n", " | Lettre C -> \"C\"\n", " | Somme (r1, r2) ->\n", " if last=\"+\" || last=\"*\" then\n", " sprintf \"%s + %s\" (to_string \"+\" r1) (to_string \"+\" r2)\n", " else\n", " sprintf \"(%s + %s)\" (to_string \"+\" r1) (to_string \"+\" r2)\n", " | Concat (r1, r2) ->\n", " if last=\".\" || last=\"*\" then\n", " sprintf \"%s . %s\" (to_string \".\" r1) (to_string \".\" r2)\n", " else\n", " sprintf \"(%s . %s)\" (to_string \".\" r1) (to_string \".\" r2)\n", " | Etoile r -> sprintf \"(%s)*\" (to_string \"*\" r)\n", ";;\n", "\n", "let regexp_to_string = to_string \"*\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Exemples :" ] }, { "cell_type": "code", "execution_count": 91, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : string = \"{}\"\n" ] }, "execution_count": 91, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = regexp_to_string Vide;;" ] }, { "cell_type": "code", "execution_count": 92, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : string = \"Epsilon\"\n" ] }, "execution_count": 92, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = regexp_to_string Epsilon;;" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : string = \"(Epsilon)*\"\n" ] }, "execution_count": 93, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = regexp_to_string (Etoile Epsilon);;" ] }, { "cell_type": "code", "execution_count": 94, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : string = \"(A + B + C)* . A . B\"\n" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string = \"B . A . (A + B + C)*\"\n" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string =\n", "\"(A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C)*\"\n" ] }, "execution_count": 94, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = regexp_to_string la1;;\n", "let _ = regexp_to_string la2;;\n", "let _ = regexp_to_string au_moins7;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 13 : `est_vide`\n", "\n", "On teste si le langage généré par l'expression régulière est vide ou non.\n", "Une étoile n'est jamais vide, même $\\varepsilon^* = \\emptyset^* = \\{\\varepsilon\\}$. " ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_vide : regexp -> bool = \n" ] }, "execution_count": 102, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec est_vide = function\n", " | Vide -> true\n", " | Epsilon -> false\n", " | Lettre _ -> false\n", " | Somme (r1, r2) | Concat (r1, r2) -> est_vide r1 && est_vide r2\n", " | Etoile _ -> false (* piège ! *)\n", ";;" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = est_vide Vide;;\n", "let _ = est_vide sigma;;\n", "let _ = est_vide la1;;\n", "let _ = est_vide la2;;" ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 104, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 104, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 104, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = est_vide (Etoile Vide);;\n", "let _ = est_vide (Etoile Epsilon);;\n", "let _ = est_vide Epsilon;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 14 : `est_fini`\n", "\n", "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\\}$**!" ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_vide_ou_epsilon : regexp -> bool = \n" ] }, "execution_count": 106, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec est_vide_ou_epsilon = function\n", " | Vide -> true\n", " | Epsilon -> true\n", " | Lettre _ -> false\n", " | Somme (r1, r2) | Concat (r1, r2) -> est_vide_ou_epsilon r1 || est_vide_ou_epsilon r2\n", " | Etoile r -> est_vide_ou_epsilon r\n", ";;" ] }, { "cell_type": "code", "execution_count": 107, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val est_fini : regexp -> bool = \n" ] }, "execution_count": 107, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec est_fini = function\n", " | Vide -> true\n", " | Epsilon -> true\n", " | Lettre _ -> true\n", " | Somme (r1, r2) | Concat (r1, r2) -> est_fini r1 && est_fini r2\n", " | Etoile r -> est_vide_ou_epsilon r\n", " (* Piège car [Etoile Vide] est fini, [Etoile Epsilon] est fini aussi ! *)\n", ";;" ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = est_fini Vide;;\n", "let _ = est_fini Epsilon;;\n", "let _ = est_fini sigma;;\n", "let _ = est_fini la1;;\n", "let _ = est_fini la2;;" ] }, { "cell_type": "code", "execution_count": 110, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = true\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : bool = false\n" ] }, "execution_count": 110, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = est_fini (Etoile Vide);;\n", "let _ = est_fini (Etoile Epsilon);;\n", "let _ = est_fini (Etoile (Somme (Epsilon, Epsilon)));;\n", "let _ = est_fini (Etoile (Somme (Vide, Epsilon)));;\n", "let _ = est_fini (Etoile (Somme (Vide, Vide)));;\n", "let _ = est_fini (Etoile (Concat (Epsilon, Epsilon)));;\n", "let _ = est_fini (Etoile (Concat (Vide, Epsilon)));;\n", "let _ = est_fini (Etoile (Concat (Vide, Vide)));;\n", "let _ = est_fini (Etoile sigma);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 15 : `pile_ou_face`\n", "\n", "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.html#VALself_init)." ] }, { "cell_type": "code", "execution_count": 111, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type piece = Pile | Face\n" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val pile_ou_face : unit -> piece = \n" ] }, "execution_count": 111, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type piece = Pile | Face;;\n", "Random.self_init ();;\n", "\n", "let pile_ou_face () =\n", " match Random.int 2 with\n", " | 0 -> Pile\n", " | 1 -> Face\n", " | _ -> failwith \"impossible\"\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple :" ] }, { "cell_type": "code", "execution_count": 113, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : piece array =\n", "[|Pile; Pile; Pile; Pile; Pile; Pile; Face; Face; Pile; Face|]\n" ] }, "execution_count": 113, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = Array.init 10 (fun _ -> pile_ou_face ());;" ] }, { "cell_type": "code", "execution_count": 114, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : piece array =\n", "[|Face; Face; Face; Pile; Pile; Face; Pile; Face; Pile; Pile|]\n" ] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = Array.init 10 (fun _ -> pile_ou_face ());;" ] }, { "cell_type": "code", "execution_count": 115, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : piece array =\n", "[|Face; Face; Pile; Pile; Pile; Face; Pile; Pile; Pile; Face|]\n" ] }, "execution_count": 115, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = Array.init 10 (fun _ -> pile_ou_face ());;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 16 : `mot_aleatoire`\n", "\n", "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.\n", "\n", "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).\n", "\n", "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.\n", "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/))." ] }, { "cell_type": "code", "execution_count": 116, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val mot_aleatoire : regexp -> lettre list = \n" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec mot_aleatoire = function\n", " | Vide -> failwith \"langage vide\"\n", " | Epsilon -> [] (* mot vide = liste de lettres vides *)\n", " | Lettre l -> [l]\n", " (* si une est vide on doit pas la choisir *)\n", " | Somme (r1, r2) when est_vide r1 -> mot_aleatoire r2\n", " | Somme (r1, r2) when est_vide r2 -> mot_aleatoire r1\n", " | Somme (r1, r2) -> begin\n", " match pile_ou_face() with\n", " | Pile -> mot_aleatoire r1\n", " | Face -> mot_aleatoire r2\n", " end\n", " | Concat (r1, r2) ->\n", " let m1 = mot_aleatoire r1 in\n", " let m2 = mot_aleatoire r2 in\n", " m1 @ m2\n", " (* Etoile (quelque chose qui est vide) devrait marcher et renvoyer vide *)\n", " | Etoile r when est_vide r -> [] (* mot vide *)\n", " | Etoile r -> begin\n", " match pile_ou_face() with\n", " | Pile -> []\n", " | Face -> (mot_aleatoire r) @ (mot_aleatoire (Etoile r))\n", " end\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut faire quelques exemples :" ] }, { "cell_type": "code", "execution_count": 117, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : lettre list = [A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [A; A; B; A; C; A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [C; A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [A; C; A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [A; A; B]\n" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = mot_aleatoire la1;;\n", "let _ = mot_aleatoire la1;;\n", "let _ = mot_aleatoire la1;;\n", "let _ = mot_aleatoire la1;;\n", "let _ = mot_aleatoire la1;;\n", "let _ = mot_aleatoire la1;;\n", "let _ = mot_aleatoire la1;;" ] }, { "cell_type": "code", "execution_count": 118, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : lettre list = [B; A; B]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A; C; C]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A; A]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A]\n" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = mot_aleatoire la2;;\n", "let _ = mot_aleatoire la2;;\n", "let _ = mot_aleatoire la2;;\n", "let _ = mot_aleatoire la2;;\n", "let _ = mot_aleatoire la2;;\n", "let _ = mot_aleatoire la2;;\n", "let _ = mot_aleatoire la2;;" ] }, { "cell_type": "code", "execution_count": 119, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : lettre list = [C; B; A; C; B; C; B]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [C; C; C; C; B; C; C; C; C]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; C; C; B; A; C; B]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; B; A; C; A; B; B; B; B]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [B; A; B; A; A; C; A; B; B]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [C; A; A; C; A; B; B; C]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : lettre list = [C; C; C; A; A; C; C]\n" ] }, "execution_count": 119, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = mot_aleatoire au_moins7;;\n", "let _ = mot_aleatoire au_moins7;;\n", "let _ = mot_aleatoire au_moins7;;\n", "let _ = mot_aleatoire au_moins7;;\n", "let _ = mot_aleatoire au_moins7;;\n", "let _ = mot_aleatoire au_moins7;;\n", "let _ = mot_aleatoire au_moins7;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "> 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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "# Calcul de $\\Sigma^k \\cap L(A)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 17 : `produit_cartesien`\n", "\n", "C'est assez simple à faire, quand on ne s'embête pas à chercher à être très efficace (sur les concaténations).\n", "Par contre, cette implémentation est efficace sur les appels récursifs, elle utilise cette fonction interne `aux` et un accumulateur `acc`.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val produit_cartesien : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list =\n", " \n" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let produit_cartesien (prod : 'a -> 'b -> 'c) (a : 'a list) (b : 'b list) : 'c list =\n", " let rec aux acc a =\n", " match a with\n", " | [] -> acc\n", " | va :: qa -> aux ((List.map (fun vb -> prod va vb) b) @ acc) qa\n", " in\n", " List.rev (aux [] a)\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple :" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : (int * string) list =\n", "[(1, \"probleme\"); (1, \"pas\"); (1, \"ok\"); (2, \"probleme\"); (2, \"pas\");\n", " (2, \"ok\")]\n" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "produit_cartesien (fun a b -> (a, b)) [1; 2] [\"ok\"; \"pas\"; \"probleme\"];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Liste de tous les mots de $\\Sigma^k$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut commencer par construire $\\Sigma^k$ comme une expression régulière, c'est très simple, mais ça ne sera pas suffisant :" ] }, { "cell_type": "code", "execution_count": 121, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sigma_k : int -> regexp = \n" ] }, "execution_count": 121, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec sigma_k (k : int) : regexp =\n", " match k with\n", " | n when n < 1 -> Vide\n", " | 1 -> sigma\n", " | n -> Concat (sigma, sigma_k (n - 1))\n", ";;" ] }, { "cell_type": "code", "execution_count": 122, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : string = \"{}\"\n" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string = \"A + B + C\"\n" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string = \"(A + B + C) . (A + B + C) . (A + B + C) . (A + B + C)\"\n" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : string =\n", "\"(A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C) . (A + B + C)\"\n" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" } ], "source": [ "regexp_to_string (sigma_k 0);;\n", "regexp_to_string (sigma_k 1);;\n", "regexp_to_string (sigma_k 4);;\n", "regexp_to_string (sigma_k 12);;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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 !)" ] }, { "cell_type": "code", "execution_count": 123, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "File \"[123]\", line 1, characters 16-17:\n", "Warning 41: A belongs to several types: lettre lettre\n", "The first one was selected. Please disambiguate if this is wrong.\n" ] }, { "data": { "text/plain": [ "val alphabet : lettre list = [A; B; C]\n" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val tous_mots_sigma_k : lettre list -> int -> mot list = \n" ] }, "execution_count": 123, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let alphabet = [A; B; C];; (* Sigma *)\n", "\n", "let rec tous_mots_sigma_k (alphabet : lettre list) (k : int) : mot list =\n", " match k with\n", " | k when k < 1 -> []\n", " | 1 -> List.map (fun lettre -> [lettre]) alphabet\n", " | k -> List.concat (\n", " List.map (\n", " fun lettre -> (\n", " List.map (fun mot -> lettre :: mot)\n", " (tous_mots_sigma_k alphabet (k - 1))\n", " )\n", " )\n", " alphabet\n", " )\n", ";;" ] }, { "cell_type": "code", "execution_count": 124, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot list = []\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : mot list = [[A]; [B]; [C]]\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : mot list =\n", "[[A; A]; [A; B]; [A; C]; [B; A]; [B; B]; [B; C]; [C; A]; [C; B]; [C; C]]\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : mot list =\n", "[[A; A; A]; [A; A; B]; [A; A; C]; [A; B; A]; [A; B; B]; [A; B; C]; [A; C; A];\n", " [A; C; B]; [A; C; C]; [B; A; A]; [B; A; B]; [B; A; C]; [B; B; A]; [B; B; B];\n", " [B; B; C]; [B; C; A]; [B; C; B]; [B; C; C]; [C; A; A]; [C; A; B]; [C; A; C];\n", " [C; B; A]; [C; B; B]; [C; B; C]; [C; C; A]; [C; C; B]; [C; C; C]]\n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = tous_mots_sigma_k alphabet 0;;\n", "let _ = tous_mots_sigma_k alphabet 1;;\n", "let _ = tous_mots_sigma_k alphabet 2;;\n", "let _ = tous_mots_sigma_k alphabet 3;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 19 : `filtre`\n", "\n", "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)." ] }, { "cell_type": "code", "execution_count": 126, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val filtre : ('a -> bool) -> 'a list -> 'a list = \n" ] }, "execution_count": 126, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec filtre (pred : 'a -> bool) (l : 'a list) : 'a list =\n", " match l with\n", " | [] -> []\n", " | h :: q when pred h -> h :: (filtre pred q)\n", " | _ :: q -> filtre pred q\n", ";;" ] }, { "cell_type": "code", "execution_count": 127, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : ('a -> bool) -> 'a list -> 'a list = \n" ] }, "execution_count": 127, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.filter;;" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int list = [2; 4]\n" ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "filtre (fun x -> x mod 2 = 0) [1; 2; 3; 4];;" ] }, { "cell_type": "code", "execution_count": 128, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int list = [2; 4]\n" ] }, "execution_count": 128, "metadata": {}, "output_type": "execute_result" } ], "source": [ "List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4];;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 20\n", "C'est très facile ! Il suffit d'utiliser la fonction `lecture` comme un prédicat binaire :" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : afd -> mot -> bool = \n" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lecture;;" ] }, { "cell_type": "code", "execution_count": 124, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sigmak_inter_LA : int -> afd -> mot list = \n" ] }, "execution_count": 124, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sigmak_inter_LA (k : int) (a : afd) : mot list =\n", " let s_k = tous_mots_sigma_k alphabet k in\n", " filtre (fun mot -> lecture a mot) s_k\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Exemples pour les deux automates du début tels que $L(A)$ soient $\\Sigma^* b a$ et $a b \\Sigma^*$.\n", "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." ] }, { "cell_type": "code", "execution_count": 126, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : mot list =\n", "[[A; A; B; A]; [A; B; B; A]; [A; C; B; A]; [B; A; B; A]; [B; B; B; A];\n", " [B; C; B; A]; [C; A; B; A]; [C; B; B; A]; [C; C; B; A]]\n" ] }, "execution_count": 126, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : mot list =\n", "[[A; B; A; A]; [A; B; A; B]; [A; B; A; C]; [A; B; B; A]; [A; B; B; B];\n", " [A; B; B; C]; [A; B; C; A]; [A; B; C; B]; [A; B; C; C]]\n" ] }, "execution_count": 126, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let _ = sigmak_inter_LA 4 fin_ba;;\n", "\n", "let _ = sigmak_inter_LA 4 debut_ab;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Automate produit (PLUS DUR)\n", "C'est plus dur mais assez guidé." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 21 : `bijection`" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "type f_intint_int = int * int -> int\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "type f_int_intint = int -> int * int\n" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type f_intint_int = (int * int -> int);;\n", "type f_int_intint = (int -> int * int);;" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "File \"[9]\", line 1, characters 15-16:\n", "Warning 27: unused variable p.\n" ] }, { "data": { "text/plain": [ "val bijection : int -> int -> f_intint_int * f_int_intint = \n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let bijection (p : int) (q : int) : f_intint_int * f_int_intint =\n", " let f (n, m) = m + n * q in\n", " let finv x =\n", " let m = x mod q and n = x / q in\n", " assert ((f (n, m)) = x);\n", " (n, m);\n", " in\n", " f, finv\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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]$." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "scrolled": false }, "outputs": [ { "data": { "text/plain": [ "val p : int = 2\n", "val q : int = 4\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val f : f_intint_int = \n", "val finv : f_int_intint = \n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "\n", "0, 0 -> 0\n", "0, 1 -> 1\n", "0, 2 -> 2\n", "0, 3 -> 3\n", "1, 0 -> 4\n", "1, 1 -> 5\n", "1, 2 -> 6\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "1, 3 -> 7\n", "0 -> 0, 0\n", "1 -> 0, 1\n", "2 -> 0, 2\n", "3 -> 0, 3\n", "4 -> 1, 0\n", "5 -> 1, 1\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let p = 2 and q = 4;;\n", "let f, finv = bijection 2 4;;\n", "\n", "for n = 0 to p - 1 do\n", " flush_all();\n", " for m = 0 to q - 1 do\n", " Printf.printf \"\\n%i, %i -> %i\" n m (f (n, m)); \n", " assert ((n, m) = finv (f (n, m)));\n", " done;\n", " flush_all();\n", "done;;\n", "\n", "for x = 0 to p*q - 1 do\n", " flush_all();\n", " let n, m = finv x in\n", " Printf.printf \"\\n%i -> %i, %i\" x n m ; \n", " assert (x = f (finv x));\n", "done;;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 22" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On utilise `produit_cartesien` pour les états finaux, une simple paire pour l'état initial, et un peu de calcul pour les transitions.\n", "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`)." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val alphabet : lettre list = [A; B; C]\n" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "val automate_produit : afd -> afd -> afd = \n" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let alphabet = [A; B; C];;\n", "\n", "let automate_produit (a1 : afd) (a2 : afd) =\n", " let p, i1, f1, d1 = a1.taille, a1.initial, a1.finals, a1.transition in\n", " let q, i2, f2, d2 = a2.taille, a2.initial, a2.finals, a2.transition in\n", " (* les bijections *)\n", " let taille = p * q in\n", " let f, finv = bijection p q in\n", " (* état initial *)\n", " let initial = f (i1, i2) in\n", " (* peut contenir des doublons, pas grave *)\n", " let finals = List.map f (produit_cartesien (fun x y -> (x, y)) f1 f2) in\n", " (* et moins trivial pour les transitions *)\n", " let transition = Array.init taille (fun ij -> (* pour l'état (i, j) *)\n", " let i, j = finv ij in\n", " (* d1.(i) est une liste de (lettre, etat) = (a, q1) pour i --a-> q1 *)\n", " let transition_i_1 = d1.(i) in\n", " (* d2.(j) est une liste de (lettre, etat) = (b, q2) pour j --b-> q2 *)\n", " let transition_j_2 = d2.(j) in\n", " (* on doit trouver les transitions avec la meme lettre et produire i --a-> f q1 q2 *)\n", " List.concat (\n", " List.map (fun lettre ->\n", " (* pour cette lettre on cherche la transition jointe qui convient, si elle existe *)\n", " if (List.mem_assoc lettre transition_i_1) && (List.mem_assoc lettre transition_j_2) then\n", " begin\n", " let q1 = List.assoc lettre transition_i_1 in\n", " let q2 = List.assoc lettre transition_j_2 in\n", " [(lettre, f(q1, q2))]\n", " end else []\n", " )\n", " alphabet)\n", " ) in\n", " { taille; initial; finals; transition }\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Exemple :" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : afd =\n", "{taille = 3; initial = 0; finals = [2];\n", " transition = [|[(A, 1)]; [(B, 2)]; [(A, 2); (B, 2); (C, 2)]|]}\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "- : afd =\n", "{taille = 3; initial = 0; finals = [2];\n", " transition =\n", " [|[(A, 0); (B, 1); (C, 0)]; [(A, 2); (B, 1); (C, 0)];\n", " [(A, 0); (B, 1); (C, 0)]|]}\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "debut_ab;;\n", "fin_ba;;" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val test_produit : afd =\n", " {taille = 9; initial = 0; finals = [8];\n", " transition =\n", " [|[(A, 3)]; [(A, 5)]; [(A, 3)]; [(B, 7)]; [(B, 7)]; [(B, 7)];\n", " [(A, 6); (B, 7); (C, 6)]; [(A, 8); (B, 7); (C, 6)];\n", " [(A, 6); (B, 7); (C, 6)]|]}\n" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let test_produit = automate_produit debut_ab fin_ba;;" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "6 -> 1, 2-rw-rw-r-- 1 lilian lilian 322 oct. 10 19:05 afd__test_produit.dot\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "digraph g {\n", " node [shape=circle];\n", " 0 -> 3 [label=A]\n", " 1 -> 5 [label=A]\n", " 2 -> 3 [label=A]\n", " 3 -> 7 [label=B]\n", " 4 -> 7 [label=B]\n", " 5 -> 7 [label=B]\n", " 6 -> 6 [label=A]\n", " 6 -> 7 [label=B]\n", " 6 -> 6 [label=C]\n", " 7 -> 8 [label=A]\n", " 7 -> 7 [label=B]\n", " 7 -> 6 [label=C]\n", " 8 -> 6 [label=A]\n", " 8 -> 7 [label=B]\n", " 8 -> 6 [label=C]\n", "}\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dot \"afd__test_produit.dot\" test_produit;;\n", "Sys.command \"ls -larth afd__test_produit.dot\";;\n", "Sys.command \"cat afd__test_produit.dot\";;" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "-rw-rw-r-- 1 lilian lilian 8,8K oct. 10 19:05 afd__test_produit.svg\n" ] }, { "data": { "text/plain": [ "- : int = 0\n" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Sys.command \"dot -Tsvg -o afd__test_produit.svg afd__test_produit.dot\";;\n", "Sys.command \"ls -larth afd__test_produit.svg\";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Automate Fini Déterministe - automate produit](afd__test_produit.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut vérifier qu'en partant de l'état $0$, on doit lire $A$ puis $B$, et ensuite on lit ce qu'on veut, puis on termine par $B$ puis $A$.\n", "\n", "L'automate produit reconnait l'intersection des deux langages, donc $L(A \\times B) = L(A) \\cap L(B) = AB \\Sigma^* \\cap \\Sigma^* BA = AB \\Sigma^* BA$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "# Conclusion\n", "\n", "Fin. À la séance prochaine. Le TP5 traitera de lambda calcul (en février)." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml 4.04.2", "language": "OCaml", "name": "ocaml-jupyter" }, "language_info": { "codemirror_mode": "text/x-ocaml", "file_extension": ".ml", "mimetype": "text/x-ocaml", "name": "OCaml", "nbconverter_exporter": null, "pygments_lexer": "OCaml", "version": "4.04.2" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "511px", "width": "251px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_section_display": "block", "toc_window_display": false }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }