(*** Corrrection - 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|] |] };;
(* automate1 reconnait les mots qui contiennent un nombre impairs de 'a'*)

let lire0 aut mot =
  let etat_courant = ref aut.initial in (* l'état courant *)
  Printf.printf "calcul : %d" aut.initial;
  for i = 0 to (String.length mot - 1) do
    begin
      let col = int_of_char mot.[i] - int_of_char 'a' in
      let nvel_etat = aut.transitions.(!etat_courant).(col) in
      etat_courant := nvel_etat; 
      Printf.printf "-%c->%d" mot.[i] nvel_etat;
    end
  done;
  Printf.printf (if aut.final.(!etat_courant) then " Accepté\n" else " Rejeté\n");
  aut.final.(!etat_courant) (* l'état d'arrivée est-il final ? *)
;;

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

(* Automates incomplets : on code l'absence de transition par -1 *)
let automate2 = { initial = 0; final = [|false; false; false; true|];
          transitions = [| [|1; -1|]; [|2; -1|]; [|3; -1|]; [|3; 3|]; |]};;
(* automate2 reconnait les mots qui commencent par 3 'a' *)

let automate3 = { initial = 1; final = [|true; false; true|];
          transitions = [| [|0; -1|]; [|0; 2|]; [|-1; 2|] |]};;
(* automate3 reconnait les mots non vides 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 = 
  try
    let etat_courant = ref aut.initial in (* l'état courant *)
    Printf.printf "calcul : %d" aut.initial;
    for i = 0 to (String.length mot - 1) do
      begin
        let col = int_of_char mot.[i] - int_of_char 'a' in
        let nvel_etat = aut.transitions.(!etat_courant).(col) in
        etat_courant := nvel_etat; 
        Printf.printf "-%c->%d" mot.[i] nvel_etat;
        if !etat_courant = -1 then raise Blocked (* blocage *)
      end
    done;
    Printf.printf (if aut.final.(!etat_courant) then " Accepté\n" else " Rejeté\n");
    aut.final.(!etat_courant) (* l'état d'arrivée est-il final ? *)
  with 
    Blocked -> Printf.printf " Bloqué\n";
    false
  ;;

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 = { initial = [0]; final = [1]; 
transitions = [| [| [0;1] ; [0] |]; [| [0;1] ; [] |] |] };;

type ens = int list;;

let affiche_ens e =
  Printf.printf "["; List.iter (fun x->Printf.printf "%d-" x) e; Printf.printf "]";;
  
let rec unionLT e1 e2 = match (e1,e2) with 
  (* union de deux listes triees sans doublon *)
  | (e, []) | ([], e) -> e
  | (elt1 :: ee1, elt2 :: ee2) -> 
    if elt1 < elt2 then elt1 :: (unionLT ee1 e2) 
    else if elt1 == elt2 then elt1 :: (unionLT ee1 ee2)  (* doublon ! *)
    else elt2 :: (unionLT e1 ee2)
  ;;

let rec interLT e1 e2 = match (e1, e2) with
  (* intersection de deux listes triees sans doublon *)
  | ([], e) | (e, []) -> []
  | (elt1 :: ee1, elt2 :: ee2) -> 
    if elt1 = elt2 then elt1::(interLT ee1 ee2)
    else if elt1 < elt2 then interLT ee1 e2
    else interLT e1 ee2
  ;;

let lireND aut mot =
    let etats_courants = ref aut.initial in (* la liste des états courants *)
    Printf.printf "lireND :"; affiche_ens !etats_courants;
    for i = 0 to (String.length mot - 1) do (* pour chaque caractère lu *)
      begin
        let col = int_of_char mot.[i] - int_of_char 'a' in
        (* on cree la liste des listes d'états obtenus par lecture du caractère *)
        let nvx_etats = ref [] in
        List.iter (fun e -> nvx_etats := unionLT !nvx_etats aut.transitions.(e).(col)) !etats_courants;
        (* nouvel ensemble d'états courants *)
        etats_courants := !nvx_etats;
        Printf.printf "-%c->" mot.[i]; affiche_ens !etats_courants;
      end
    done;
    (* vérification finale *)
    let reconnu = interLT !etats_courants aut.final <> [] in
    Printf.printf (if reconnu then " Accepté\n" else " Rejeté\n"); reconnu
  ;;

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