Crash after pruning NFA...

[Kakadu]

@toodom02, Am I missing something obvious?

let () =
  let ast = Re.parse "b*" in
  let nfa = ast |> Regextkit.Nfa.re_to_nfa in
  Regextkit.Nfa.prune nfa;
  let _dfa = Regextkit.Dfa.nfa_to_dfa nfa in
  ()
;;

Fatal error: exception Not_found
Raised at StdlibHashtbl.find in file "hashtbl.ml", line 539, characters 13-28 Called from RegextkitAdt.get_next_states in file "ocamlregextkit/lib/adt.ml", line 54, characters 45-75 Called from RegextkitNfa.eps_reachable_set.get_reachable_set.(fun) in file "ocamlregextkit/lib/nfa.ml", line 80, characters 41-71 Called from RegextkitNfa.eps_reachable_set in file "ocamlregextkit/lib/nfa.ml", line 86, characters 19-43 Called from RegextkitDfa.nfa_to_dfa in file "ocamlregextkit/lib/dfa.ml", line 476, characters 17-56 Called from Duneexe__Demo2 in file "ocamlregextkit/demo/demo2.ml", line 7, characters 13-41

[toodom02]

Appears to be an error in pruning, where our state marking to find reachable states does not consider epsilon transitions (so misses the case where a state is only reachable by epsilon).

Should be a simple fix to the get_reachable_states function in adt.ml (change to line 78), to include epsilon when looking for transitions:

let get_reachable_states m =
  let rec find_reachable_states marked =
    let newmarked =
      List.fold_left
        (fun acc s ->
          List.fold_left
            (fun acc2 a -> Utils.list_union acc2 (get_next_states m s a))
            acc
            ("ε"::m.alphabet))
        marked
        marked
    in
    if marked <> newmarked then find_reachable_states newmarked else newmarked
  in
  find_reachable_states [ m.start ]
;;

Will test properly and merge when I have chance. Thanks for raising issue