(*** TP Automates ***)

(* on suppose l'alphabet a,b *)

type automaton = { (* n : le nombre d'états, 0 à n-1 *)
  initial : int; (* l'état initial *)
  final : bool array; (* tableau de n booléens *)
  transitions : int array array; (* tableau n lignes, 2 colonnes *)
  (* colonne 0 : transition à la lecture de 'a' *)
  (* colonne 1 : transition à la lecture de 'b' *)
}

(* Automate complet *)

let automate1 = { initial = 0; final = [|false;true|]; 
transitions = [| [|1;0|]; [|0;1|] |] };;

let lire0 aut mot = failwith "A implémenter";;

assert(lire0 automate1 "baabba");;
assert(not (lire0 automate1 "abba"));;


(* Automates incomplets : on code l'absence de transition par -1 *)
let automate2 = failwith "A définir";;
(* automate2 reconnait les mots qui commencent par 3 'a' *)

let automate3 = failwith "A définir";;
(* automate3 reconnait les mots qui ne contiennent que des 'a' ou que des 'b' *)


exception Blocked;; (* exception pour gérer le blocage de l'automate *)

let lire aut mot = failwith "A implémenter";;

assert(lire automate1 "baabba");;
assert(not (lire automate1 "abba"));;

assert(not (lire automate2 "aa"));;
assert(not (lire automate2 "baaaa"));;
assert(lire automate2 "aaa");;
assert(lire automate2 "aaabaabba");;

assert(lire automate3 "aa");;
assert(not (lire automate3 "baaaa"));;
assert(lire automate3 "bbbb");;
assert(not (lire automate3 "bbaabba"));

(* Automate non déterministe *)

type automatonND = { (*n : le nombre d'états, numérotés de 0 à n-1 *)
  initial : int list; (* les états initiaux *)
  final : int list; (* les états finaux *)
  transitions : int list array array; (* n lignes, 2 colonnes *)
}

let automateND1 = { initial = [0]; final = [2]; 
transitions = [| [| [0;1] ; [] |]; [| [2] ; [0;2] |] ; [| [] ; [] |] |] };;

let automateND2 = failwith "A définir";;

type ens = int list;;

let rec unionLT e1 e2 = match (e1,e2) with 
  (* union de deux listes triees sans doublon *)
  | _ -> failwith "A faire"
  ;;

let rec interLT e1 e2 = match (e1, e2) with
  (* intersection de deux listes triees sans doublon *)
  | _ -> failwith "A faire"
;;

let affiche_ens e =
  Printf.printf "["; List.iter (fun x->Printf.printf "%d-" x) e; Printf.printf "]";;



let lireND aut mot = failwith "A implémenter"
;;

assert (lireND automateND1 "aaa");;
assert (not (lireND automateND1 "abbaa"));;
assert (lireND automateND2 "abbaa");;
assert (not (lireND automateND1 "bbaab"));;