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'