type etat = int;;
type liste_etats = etat list;;

type symbole = int;;
type mot = symbole list;;

type afnd = { initiaux : liste_etats;
              terminaux : liste_etats;
              delta : liste_etats array array };;

let union lst1 lst2 = match lst2 with
  | [] -> ...
  | t::q when List.mem t lst1 -> ...
  | t::q -> ... ;;

let intersection lst1 lst2 = match lst2 with
  | [] -> ...
  | t::q when List.mem t lst1 -> ...
  | t::q -> ... ;;

let lit_car automate etats c =
  ... ;;

let lit_mot automate etats c =
  ... ;;

let teste automate w =
  ... ;;

let construit_local p ens_p ens_s ens_f =
  ... ;;

let p1 = [1; 2] and s1 = [0] and f = [(0,1); (0,2); (1,0); (1,2); (2,0); (2,1)];;

let automate1 = construit_local 3 p1 s1 f1;;

type regexp =
  | Constante of int list
  | Etoile of regexp
  | Concatenation of regexp * regexp
  | Choix of regexp * regexp;;

let rec contientMotVide = function
  | Constante [] -> true
  | Constante _ -> false
  | Etoile e -> true
  | Concatenation (e,f) -> contientMotVide e && contientMotVide f
  | Choix (e,f) -> contientMotVide e || contientMotVide f;;

let rec prefixes = function
  | Constante [] -> []
  | Constante lst -> [ List.hd lst ]
  | Etoile e -> prefixes e
  | Concatenation (e,f) when contientMotVide e -> prefixes e @ prefixes f
  | Concatenation (e,f) -> prefixes e
  | Choix (e,f) -> prefixes e @ prefixes f;;

let rec suffixes = function
  | Constante [] -> []
  | Constante lst -> [ List.hd (List.rev lst) ]
  | Etoile e -> suffixes e
  | Concatenation (e,f) when contientMotVide f -> suffixes e @ suffixes f
  | Concatenation (e,f) -> suffixes f
  | Choix (e,f) -> suffixes e @ suffixes f;;

let rec produit = function
  | ([], _) -> []
  | (_, []) -> []
  | (t::q, lst) -> List.map (fun c -> (t, c)) lst @ (produit (q, lst));;

let rec facteurs2 = function
  | Constante lst -> let rec paires = function
                       | t1::t2::q -> (t1, t2)::paires (t2::q)
                       | _ -> []
                     in paires lst
  | Etoile e -> (facteurs2 e) @ (produit (suffixes e, prefixes e))
  | Concatenation (e,f) -> (facteurs2 e) @ ((facteurs2 f)
                           @ (produit (suffixes e, prefixes f)))
  | Choix (e,f) -> (facteurs2 e) @ (facteurs2 f);;

let r2 = Concatenation (Etoile (Choix (Constante [0], Constante [1; 2])),
                        Concatenation (Etoile (Constante [3]), (Constante [4])));;

type afd = { initial : etat;
             terminaux : liste_etats;
             delta : etat array array };;

let teste_afd automate mot =
  List.mem (List.fold_left (fun q c -> automate.delta.(q).(c)) automate.initial mot)
           automate.terminaux;;