NFA -> DFA
まだなんとなくカッコわるいが、NFA から DFA の変換。
powerSet [] = [[]] powerSet (x:xs) = yss ++ map (x:) yss where yss = powerSet xs subset :: Set.Set State -> Set.Set State subset states = Set.fromList (map (\x -> S'' (Set.fromList x)) (powerSet (Set.elems states))) convertToDfa :: Nfa0 -> Dfa convertToDfa (Nfa0 (qs, cs, d, q0, fs)) = Dfa (qs', cs', d', q0', fs') where extractS (S'' s) = Set.elems (s) isAccept s = any (\x -> Set.member x fs) (extractS s) qs' = subset qs cs' = cs d' = [ ((r, c), S'' (Set.unions [ (transitNfa d r' c) | r' <- extractS r ])) | r <- Set.elems(qs'), c <- Set.elems(cs)] q0' = S'' (Set.singleton q0) fs' = Set.filter isAccept qs'