メモ

すごいHaskell 本を読んだりしながら、オートマトンを書き換えている。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.9852 "A Taxonomy of Finite Algorithms (1993) by Bruce Watson を参考に、オートマトンは５つ組ではなく、ε-遷移を通常の遷移と分けた６つ組とした。骨格は以下の通り。

type Symbol = Char
-- Fintite Automaton type
type States a = Set a
type Alphabet = Set Symbol
type Transition a = Set (Labelled a)
type ETransition a = Set (Epsilon a)

-- Labelled fromState Symbol toState
data Labelled a = Labelled a Symbol a deriving (Eq, Ord)
-- Epsilon fromState toState
data Epsilon a = Epsilon a a deriving (Eq, Ord)

data FA a = FA
    (States a) -- A finite set of states. Q
    Alphabet -- A finite set of symbol (alphabet). V
    (Transition a) -- A set of transition. T
    (ETransition a) -- A set of epsilon-transition. E
    (States a) -- A set of start state. S 
    (States a) -- A set of accept states. F

isDet :: (Ord a) => FA a -> Bool
isDet m@(FA qset cset tset eset q0set fset) = 
    S.size q0set <= 1 && -- does not have multiple start states
    isEfree m &&
    -- map to single states
    all (<= 1) [ S.size (transit tset q c) | q <- elems qset, c <- elems cset ]

transit1 :: (Ord a) => Transition a -> a -> Symbol -> a
transit1 t q c = elem1 (transit t q c)

isString :: Ord a => FA a -> [Symbol] -> Bool
isString (FA _ cset _ _ _ _) = all (`S.member` cset)

accept :: (Ord a) => FA a -> [Symbol] -> Bool
accept m@(FA qset cset tset eset q0set fset) str
    | isDet m && isString m str = S.member (foldl (transit1 tset) (elem1 q0set) str) fset

accept m str = error "Not implmented NFA accept or invalid string."