1. (*** TP Automates ***)
  2.  
  3. (* on suppose l'alphabet a,b *)
  4.  
  5. type automaton = { (* n : le nombre d'états, 0 à n-1 *)
  6.   initial : int; (* l'état initial *)
  7.   final : bool array; (* tableau de n booléens *)
  8.   transitions : int array array; (* tableau n lignes, 2 colonnes *)
  9.   (* colonne 0 : transition à la lecture de 'a' *)
  10.   (* colonne 1 : transition à la lecture de 'b' *)
  11. }
  12.  
  13. (* Automate complet *)
  14.  
  15. let automate1 = { initial = 0; final = [|false;true|]; 
  16. transitions = [| [|1;0|]; [|0;1|] |] };;
  17.  
  18. let lire0 aut mot = failwith "A implémenter";;
  19.  
  20. assert(lire0 automate1 "baabba");;
  21. assert(not (lire0 automate1 "abba"));;
  22.  
  23.  
  24. (* Automates incomplets : on code l'absence de transition par -1 *)
  25. let automate2 = failwith "A définir";;
  26. (* automate2 reconnait les mots qui commencent par 3 'a' *)
  27.  
  28. let automate3 = failwith "A définir";;
  29. (* automate3 reconnait les mots qui ne contiennent que des 'a' ou que des 'b' *)
  30.  
  31.  
  32. exception Blocked;; (* exception pour gérer le blocage de l'automate *)
  33.  
  34. let lire aut mot = failwith "A implémenter";;
  35.  
  36. assert(lire automate1 "baabba");;
  37. assert(not (lire automate1 "abba"));;
  38.  
  39. assert(not (lire automate2 "aa"));;
  40. assert(not (lire automate2 "baaaa"));;
  41. assert(lire automate2 "aaa");;
  42. assert(lire automate2 "aaabaabba");;
  43.  
  44. assert(lire automate3 "aa");;
  45. assert(not (lire automate3 "baaaa"));;
  46. assert(lire automate3 "bbbb");;
  47. assert(not (lire automate3 "bbaabba"));
  48.  
  49. (* Automate non déterministe *)
  50.  
  51. type automatonND = { (*n : le nombre d'états, numérotés de 0 à n-1 *)
  52.   initial : int list; (* les états initiaux *)
  53.   final : int list; (* les états finaux *)
  54.   transitions : int list array array; (* n lignes, 2 colonnes *)
  55. }
  56.  
  57. let automateND1 = { initial = [0]; final = [2]; 
  58. transitions = [| [| [0;1] ; [] |]; [| [2] ; [0;2] |] ; [| [] ; [] |] |] };;
  59.  
  60. let automateND2 = failwith "A définir";;
  61.  
  62. type ens = int list;;
  63.  
  64. let rec unionLT e1 e2 = match (e1,e2) with 
  65.   (* union de deux listes triees sans doublon *)
  66.   | _ -> failwith "A faire"
  67.   ;;
  68.  
  69. let rec interLT e1 e2 = match (e1, e2) with
  70.   (* intersection de deux listes triees sans doublon *)
  71.   | _ -> failwith "A faire"
  72. ;;
  73.  
  74. let affiche_ens e =
  75.   Printf.printf "["; List.iter (fun x->Printf.printf "%d-" x) e; Printf.printf "]";;
  76.  
  77.  
  78.  
  79. let lireND aut mot = failwith "A implémenter"
  80. ;;
  81.  
  82. assert (lireND automateND1 "aaa");;
  83. assert (not (lireND automateND1 "abbaa"));;
  84. assert (lireND automateND2 "abbaa");;
  85. assert (not (lireND automateND1 "bbaab"));;
  86.