type tomate = {initial: int; delta: int->char->int; est_final: int->bool};;

let deltastar i c = if (i=0) && (c='a') then 0 else 1;;
let astar = {initial= 0; delta= deltastar; est_final= (fun i -> (i=0))};;

let elang = {initial= 0; delta= (fun i c -> 1); est_final=fun i -> i=0};;
let zerolang = {initial= 0; delta= (fun i c -> 0); est_final=fun i -> false};;

let estReconnu tom s = let etat = ref tom.initial in
	for i=0 to ((String.length s) -1)
	do
		etat := tom.delta !etat s.[i]
	done;
	tom.est_final !etat;;

let langTrois = {
	initial=0;
	delta= (fun i c -> match (i,c) with
		| (0,'a') -> 1
		| (1,'a') -> 2
		| (2,'a') -> 2
		| (2,'b') -> 3
		| (3,'a') -> 2
		|    _    -> 42);
	est_final = fun i -> (i=3)
};;

let rec ln2 i = match i with
	| 0|1 -> 0
	| n -> 1+(ln2 (n/2));;
let int2bin n = let s = ln2 n in 
	let out = String.make (s+1) '0'
	and nn = ref n in
	for i=0 to s do
		if !nn mod 2 = 1
		then Bytes.set out (s-i) '1';
		nn := !nn/2
	done;
	out;;
	
let troitomate = {
	initial=0;
	delta= (fun i c -> match (i,c) with
		| (0,'0') -> 0
		| (0,'1') -> 1
		| (1,'0') -> 2
		| (1,'1') -> 0
		| (2,'0') -> 1
		| (2,'1') -> 2
		|    _    -> 42);
	est_final = fun i -> (i=0)
};;

let divisibleParTrois n = estReconnu troitomate (int2bin n);;


(*** TESTS ***)
estReconnu astar "";;
estReconnu astar "aaa";;
estReconnu astar "a";;
estReconnu astar "abaa";;
estReconnu astar "bbb";;
estReconnu elang "";;
estReconnu elang "aa";;
estReconnu langTrois "aab";;
estReconnu langTrois "";;
estReconnu langTrois "aababababaaababaaababab";;
estReconnu langTrois "aa";;
estReconnu langTrois "aabbab";;
estReconnu langTrois "aababab";;
estReconnu langTrois "aaaab";;
estReconnu langTrois "aab";;
estReconnu langTrois "aababababaababaabaaaabaaba";;
int2bin 42;;
for i=0 to 42 do
	print_string (string_of_int i);
	print_string " -> ";
	print_endline (string_of_bool (divisibleParTrois i))
done;;



(*** PARTIE 2***)

let rec insere e l = match l with
	| [] -> [e]
	| t::q -> if t<=e then e::t::q else t::(insere e q);;

let rec egal a b = match (a,b) with
	| ([],[]) -> true
	| (ae::a2,be::b2) -> ae=ae && (egal a2 b2)
	| _ -> false;;

let rec estdans e l = match l with
	| [] ->  false
	| t::s -> (e=t) || (not e>t) && (estdans e s);;

type totomate = {
	etats: int list;
	initiaux: int list;
	finaux: int list;
	transitions: (int*char*int) list
};;

let asastar = {
	etats = [0];
	initiaux = [0];
	finaux = [0];
	transitions = [(0,'a',0)]
};;

let eleltrans = 
	let rec aux l i = match i with
		| 0 -> (0,(Char.chr i),1)::l
		| n -> aux ((0,Char.chr n,1)::l) (n-1) in
	aux [] 127;;

let elelang = {
	etats= [0;1];
	initiaux = [0];
	finaux = [0];
	transitions = eleltrans
};;
let zezerolang = {initial= 0; delta= (fun i c -> 0); est_final=fun i -> false};;