Haskell でオートマトン(4)
一度クラスを導入してみたが、あまりにややこしくなってしまった。迷走ぎみだが、シンプルに書き換えた。
module Fa where import System.Environment data State = State String deriving (Eq, Show) type Symbol = Char type Alphabet = [Symbol] -- Dfa states alphabet transition-function "start state" "accept states" data Dfa = Dfa [State] Alphabet [((State, Symbol), State)] State [State] deriving (Show, Eq) statesOf (Dfa a _ _ _ _) = a alphabetOf (Dfa _ a _ _ _) = a transitOf (Dfa _ _ a _ _) = a startOf (Dfa _ _ _ a _) = a acceptOf (Dfa _ _ _ _ a) = a -- transitDfa :: Dfa -> State -> Symbol -> State transitDfa dfa s0 a0 = case lookup (s0, a0) (transitOf dfa) of Just s -> s Nothing -> error "invalid transition" -- accept' :: Dfa -> [Symbol] -> Bool accept dfa str = accept' dfa (startOf dfa) str where accept' dfa s [] = elem s (acceptOf dfa) accept' dfa s (c:cs) = accept' dfa s' cs where s' = transitDfa dfa s c -- accept odd number of 'a' s dfa1 = Dfa [State "q0", State "q1"] -- states "ab" -- alphabet [ ((State "q0", 'a'), State "q1"), ((State "q0", 'b'), State "q0"), ((State "q1", 'a'), State "q0"), ((State "q1", 'b'), State "q1")] -- transition function (State "q0") -- start state [State "q1"] -- accept states