Haskell でオートマトン
Haskell の勉強のため、オートマトン(DFA)を書いてみた。まずは簡単な例として、奇数個の 'a' を受理するオートマトン(http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/07/automaton/k2.pdf より)。汎用性は全く無視。
module Fa where import System.Environment data State = Even | Odd deriving (Eq, Show) transit Even 'a' = Odd transit Even 'b' = Even transit Odd 'a' = Even transit Odd 'b' = Odd accept Odd [] = True accept _ [] = False accept s (c:cs) = accept (transit s c) cs
こんな感じで動かす。
*Fa> accept Even "aa" False *Fa> accept Even "a" True *Fa> accept Even "aaa" True *Fa> accept Even "aababb" True *Fa> accept Even "aababba" False *Fa>