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