有限オートマトンと Haskell

有限オートマトンで作った奇数判定機
『オートマトン・言語理論の基礎』米田政明監修 p38

  a->
q0   q1(受理)
  <-a

M = 
Q = {q0, q1}
Σ = {a}
δ = {q0 x a -> q1
     q1 x a -> q2}
F = {q1}

このような表記法がメチャクチャ嫌いではあるので、Haskell で表現してみる。

data InputChar = A
data State = Q0 | Q1 deriving (Eq)

move :: State -> InputChar -> State
move Q1 A = Q0 -- Q0 から A を食って Q1 に遷移する
move Q0 A = Q1 -- Q1 から A を食って Q0 に遷移する

process :: State -> State -> [InputChar] -> Bool
process start goal (x:xs)           = process (move start x) goal xs
process state end [] | state == end = True -- 全部読み込んだ結果
                     | otherwise    = False

machine = process Q0 Q1 -- スタートとゴールを設定

# 実行
Automata> machine [A,A,A,A]
False
Automata> machine [A,A,A]
True

prolog 版。こっちの方が綺麗かな?

move(q0, a, q1).
move(q1, a, q0).

machine(X) :- machine(q0, X, q1).  % スタートとゴールを決める
machine(Last, [], Last).           % ゴールまで来れば成功
machine(First, [X | XS], Last) :-
    move(First, X, Next),          % 現在のシンボルがルールにあるか?
    machine(Next, XS, Last).       % あれば次の文字をチェック

?- machine([a,a,a,a,a]). 
Yes