130 lines
2.7 KiB
OCaml
130 lines
2.7 KiB
OCaml
|
|
|
|
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};;
|
|
|
|
|
|
|