1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
include List
type letter = string
type alphabet = letter list
type state = int
type transition = state * letter * state
type trans_func = transition list
type regex =
| Empty
| Epsilon
| Letter of letter
| Plus of regex * regex
| Concat of regex * regex
| Star of regex
(* <E, Q, q0, d, F> *)
type automaton = Automaton of alphabet * (state list) * state * trans_func * (state list)
let rec big_plus letters =
match letters with
| [] -> Empty
| "" :: [] -> Epsilon
| l :: [] -> Letter l
| "" :: tl -> Plus (Epsilon, big_plus tl)
| l :: tl -> Plus ((Letter l), (big_plus tl))
let basic_regexes states delta =
let get_letters_aux s1 s2 =
List.map
(fun (w,l,v) -> l)
(List.filter (fun (w,l,v) -> w = s1 && v = s2) delta)
in let get_letters s1 s2 =
let res = (get_letters_aux s1 s2) in
if s1 = s2 then "" :: res else res
in let gen_basic state =
List.map big_plus (List.map (get_letters state) states)
in List.map gen_basic states
let s = [0;1;2;3;4];;
let delta = [ (0, "a", 0); (0, "b", 1);
(1, "a", 2); (1, "b", 1);
(2, "a", 0); (2, "b", 3);
(3, "a", 4); (3, "b", 1);
(4, "a", 4); (4, "b", 4)]
let rec iter_list = function
| 0 -> [0]
| n -> n :: iter_list (n - 1)
let rec iter n = List.rev (iter_list (n-1))
let increment_phis states_num regexes k =
let ijth i j = (List.nth (List.nth regexes i) j) in
let increment_regex i j =
let rij = (ijth i j) in
let rik = (ijth i k) in
let rkk = (ijth k k) in
let rkj = (ijth k j) in
Plus (rij, Concat (rik, Concat (Star rkk, rkj))) in
let incr_for_i i = List.map (fun j -> increment_regex i j) (iter states_num) in
List.map incr_for_i (iter states_num)
let get_results states_num delta =
let states = iter states_num in
let regexes = basic_regexes states delta in
let rec update_regexes regexes k =
if k = states_num then regexes else
update_regexes (increment_phis states_num regexes k) (k+1) in
update_regexes regexes 1
let rec string_of_regex regex =
match regex with
| Empty -> "∅"
| Epsilon -> "ε"
| Letter l -> l
| Plus (phi1, phi2) -> "(" ^ (string_of_regex phi1) ^ ") + (" ^ (string_of_regex phi2) ^ ")"
| Concat (phi1, phi2) -> (string_of_regex phi1) ^ (string_of_regex phi2)
| Star phi -> "(" ^ (string_of_regex phi) ^ ")*"
let pp_print_regex fmtr f =
Format.pp_print_string fmtr (string_of_regex f)
|
