module OrderedType (T: sig type t end) = struct
  type t = T.t
  let compare = compare
end

module CM = Map.Make(Char)
module State = OrderedType (struct type t = int end)
module S = Set.Make(State)
module SM = Map.Make(State)
module SS = Set.Make(S)
module SSM = Map.Make(S)

type dfa_t = { dm: S.t CM.t SSM.t; dinit: S.t; dacc: SS.t; }
type nfa_t = { nm: S.t CM.t SM.t; ninit: State.t; nacc: S.t; }

let id x = x

let mapunion = CM.merge (fun _ -> function
  | None -> (function | None -> None | Some s2 -> Some s2)
  | Some s1 -> (function | None -> Some s1 | Some s2 -> Some (S.union s1 s2)))

let nfa2dfa nfa =
  let dfamap nm ninit =
    let rec dfs ss (dfa, seen) =
      if SS.mem ss seen then (dfa, seen)
      else let dmap = S.fold (fun s -> mapunion (SM.find s nm)) ss CM.empty in
           CM.fold (fun _ -> dfs) dmap (SSM.add ss dmap dfa, SS.add ss seen)
    in fst (dfs (S.singleton ninit) (SSM.empty, SS.empty))
  and dfacc dm nacc =
    SSM.fold (fun ss _ -> if S.inter ss nacc = S.empty then id else SS.add ss) dm SS.empty
  in let dm = dfamap nfa.nm nfa.ninit
     in { dm = dm; dinit = S.singleton nfa.ninit; dacc = dfacc dm nfa.nacc }
     

This document was generated using caml2html