有限オートマトン

よく考えたら遷移関数はただのグラフだった。グラフの隣接リスト表現で十分だ。マクロをちょっと書き換え、名前を付けられるようにし、ほとんどこれ以上短くできないようにした。

(defmacro def-dfa (name (states alphabet transition init-state final-states))
  (let ((string (gensym "string"))
        (state (gensym "state"))
        (symbol (gensym "symbol")))
    `(defun ,name (,string)
       (let ((,state ,init-state))
         #'(lambda ()
             (cond
               ((null ,string)
                (if (member ,state ',final-states)
                    (values nil ,state 'accept)
                    (values nil ,state 'not-accept)))
               (t
                (let ((,symbol (pop ,string)))
                  (assert (member ,symbol ',alphabet))
                  (setf ,state
                        (ecase ,state
                          ,@(loop for (s . adj) in transition
                               collect `(,s (ecase ,symbol ,@adj)))))
                  (assert (member ,state ',states))
                  (values ,symbol ,state)))))))))

(defun run-dfa (dfa)
  (multiple-value-bind (a state acceptp) (funcall dfa)
    (format t ";; a: ~a state: ~a~%" a state)
    (if a
      (run-dfa dfa)
      acceptp)))

;; accept x01y | x, y {0,1}*
(def-dfa a ((:q0 :q1 :q2) (0 1)
            ((:q0
              (0 :q2)
              (1 :q0))
             (:q1
              (0 :q1)
              (1 :q1))
             (:q2
              (0 :q2)
              (1 :q1)))
            :q0 (:q1)))

;; 0 and 1 oocurs even time
(def-dfa even-0-1-automaton ((:q0 :q1 :q2 :q3) (0 1)
                             ((:q0
                               (0 :q2)
                               (1 :q1))
                              (:q1
                               (0 :q3)
                               (1 :q0))
                              (:q2
                               (0 :q0)
                               (1 :q3))
                              (:q3
                               (0 :q1)
                               (1 :q2)))
                             :q0 (:q0)))

マクロ def-dfa は名前と 有限オートマトンの定義通りに５個組の情報を受け取り、関数を定義する。その関数は１引数で"アルファベット"からなる"文字列"をリストとして受け取る。関数に文字列を与えて実行すると、引数なしのクロージャを返す。このクロージャは実行するたびに文字列から文字を一つ取り出し、次の状態に遷移する。文字列が無くなったとき、受理状態かどうかを判定する。遷移関数はグラフの隣接リスト表現で与えられる（が、実際上は唯の case 文のようにしかみえないな、、）。

SECD> (run-dfa (even-0-1-automaton '(1 1 1 0 0 0 0 1)))
;; a: 1 state: Q1
;; a: 1 state: Q0
;; a: 1 state: Q1
;; a: 0 state: Q3
;; a: 0 state: Q1
;; a: 0 state: Q3
;; a: 0 state: Q1
;; a: 1 state: Q0
;; a: NIL state: Q0
ACCEPT
SECD> (run-dfa (even-0-1-automaton '(1 1 1 0 0  0 1)))
;; a: 1 state: Q1
;; a: 1 state: Q0
;; a: 1 state: Q1
;; a: 0 state: Q3
;; a: 0 state: Q1
;; a: 0 state: Q3
;; a: 1 state: Q2
;; a: NIL state: Q2
NOT-ACCEPT
SECD> 

「計算理論の基礎　１オートマトンと言語」という本がとても良さそうなので、しばらくこれにそって急いでオートマトンを動かそう。