dc-mak
November 9, 2018, 10:38am
18
Here’s something I wrote using the Dragon Book and Standard ML yonks ago. A good exercise would be to translate it to OCaml, clean it up and use more library (standard or Base) functions.
(* Invariant: always one start state and one end state. *)
type nfa = {n : int, (* number of states *)
s : int, (* start state *)
t : (int * char * int) list, (* transitions for non-empty characters *)
d : (int * int) list, (* epsilon-transitions *)
f : int}; (* end state *)
datatype regex = Union of regex * regex
| Concat of regex * regex
| Star of regex
| Char of char option;
fun disjoint ({n,s,t,d,f}, m) =
{n = n, s = s+m, f = f+m,
d = map (fn (x,y) => (x+m, y+m)) d,
t = map (fn (x,a,y) => (x+m, a, y+m)) t}
(* construct : regex -> nfa *)
(* one start state that is accepting *)
show original