CS计算机代考程序代写 open P3.Nfa

open P3.Nfa
open P3.Regexp

let string_of_int_list lst =
“[” ^ String.concat “;” (List.map string_of_int lst) ^ “]”

let string_of_int_list_list lst =
“[” ^ String.concat “;” (List.map string_of_int_list lst) ^ “]”

let init_str =
“digraph G {
rankdir=LR; ”
^ string_of_int (Hashtbl.hash “-1″)
^ ” [style=”invis”];
”

let end_str = “
}”

let nodup x lst = if List.mem x lst then lst else x :: lst

let string_of_vtx _ lst =
List.fold_left
(fun acc (v, f) ->
let shape = if f then “doublecircle” else “circle” in
acc
^ Printf.sprintf “%d [label=”%s”,shape=%s];
” (Hashtbl.hash v) v shape
)
“” lst

let string_of_ed _ lst =
List.fold_left
(fun acc ((s1, _), c, _, (s2, _)) ->
acc
^ Printf.sprintf “%d -> %d [label=”%s”];
” (Hashtbl.hash s1)
(Hashtbl.hash s2) c )
“” lst

let write_nfa_to_graphviz (show : ‘q -> string) (nfa : (‘q, char) nfa_t) : bool
=
let name = “output.viz” in
let ss, fs, ts = (nfa.q0, nfa.fs, nfa.delta) in
let sv = (show ss, List.mem ss fs) in
let vt, ed =
List.fold_left
(fun (vt, ed) (v1, c, v2) ->
let v1′ = (show v1, List.mem v1 fs) in
let v2′ = (show v2, List.mem v2 fs) in
let c’ = match c with None -> “ε” | Some x -> String.make 1 x in
let pair = List.mem (v2, c, v1) ts in
let e = (v1′, c’, pair, v2′) in
(nodup v2′ (nodup v1′ vt), nodup e ed) )
([], []) ts
in
let ed = ((“-1″, false), ” “, false, (show ss, List.mem ss fs)) :: ed in
let dot =
init_str ^ string_of_vtx show (sv :: vt) ^ string_of_ed show ed ^ end_str
in
let file = open_out_bin name in
output_string file dot ;
flush file ;
Sys.command (Printf.sprintf “dot %s -Tpng -o output.png && rm %s” name name)
= 0

;;
print_string “Type regexp to visualize: ”

let line = read_line ()

;;
print_string “Convert to DFA (y/n)? ”

let line2 = read_line ()

let nfa = string_to_nfa line

;;
if line2 = “n” then
if write_nfa_to_graphviz string_of_int nfa then
print_string “Success! Open ‘output.png’ to see your visualized NFA.
”
else
print_string
“Failure! Are you sure you have graphviz installed on your machine?
”
else if write_nfa_to_graphviz string_of_int_list (nfa_to_dfa nfa) then
print_string “Success! Open ‘output.png’ to see your visualized DFA.
”
else
print_string
“Failure! Are you sure you have graphviz installed on your machine?
”