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

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