2010年2月28日日曜日

CommonLispで決定性有限オートマトン(DFA)

オートマトンの書籍を読んでいるので、CommonLispでDFAを定義してみる。

とりあえず目標として、記号列が(c c)で終わるものを受理するようなDFAを目指す。

(defmacro define-dfa (name (&rest ends) &body defs)
`(let ((table ',defs))
(defmethod accept-p ((type (eql ',name)) sym)
(find sym ',ends))
(defmethod next-state ((type (eql ',name)) input crr)
(let ((al (cdr (assoc crr table))))
(and al
(second (assoc input al)))))
(defmethod run ((type (eql ',name)) syms begin)
(let ((last begin))
(loop
:for sym in syms
:for state = last
:do (setf last (next-state type sym state))
:unless last
:do (return-from run :reject))
(if (accept-p type last)
:accept :reject)))))

正直ただしいのかわからない。

以下、DFAの定義。

(define-dfa cc (:end)
(:0
(a :0)
(b :0)
(c :1))
(:1
(a :0)
(b :0)
(c :end))
(:end
(a :0)
(b :0)
(c :end)))

存在する記号はa,b,cの3種類。記号列はリスト形式で受け取る。現在の状態と入力の組に対して、次の状態が存在しなければそこで処理を終了する。リスト内の要素すべてを処理したら、最終的な状態が受理状態であるかを調べる。

以下、実行例。

>(run 'cc '(c) :0)
:REJECT
>(run 'cc '(c c) :0)
:ACCEPT
>(run 'cc '(a b c) :0)
:REJECT
>(run 'cc '(a b c c) :0)
:ACCEPT
>(run 'cc '(a b c c c c) :0)
:ACCEPT
>(run 'cc '(a b c c a) :0)
:REJECT

ぱっと見た感じではうまく動いているような気がする。気のせいかもしれないけれど。

0 件のコメント:

コメントを投稿