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>