DFA 決定性有限オートマトン

オートマトンを勉強しよう。古典で基礎なので資料は山ほどある。だが基礎だから理解しているかというとそんなことはなかったので、手を動かした。

http://www.sakabe.nuie.nagoya-u.ac.jp/~sakai/lecture/automata/ オートマトン・形式言語および演習より。

以下のように実装した。

• 集合はリストで表す
• 状態はキーワード(:q0, :q1, etc)で表す
• 遷移関数は新しい状態を返す２引数関数（状態とアルファベット）

• 関数 make-dfa は引数なし関数を生成する。
• 関数 run-dfa は 文字を消費しつされるまで繰り返し DFA を実行。状態が受理状態に含まれていれば accept そうでなければ not-accept

(defun make-dfa (states alphabet transition state final-states string)
  #'(lambda ()
      (cond
        ((null string)
         (if (member state final-states)
             (values nil state 'accept)
             (values nil state 'not-accept)))
        (t
         (let ((a (pop string)))
           (assert (member a alphabet))
           (setf state (funcall transition state a))
           (assert (member state states))
           (values a 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)))

L = {x01y | x, y ∈ {0, 1}* } を認識するオートマトン A

SECD> (run-dfa (make-dfa '(:q0 :q1 :q2) ;; states
                         '(0 1) ;; alphabet
                         #'(lambda (q a) ;; transition return new state
                             (ecase q
                               (:q0
                                (ecase a
                                  (0 :q2)
                                  (1 :q0)))
                               (:q1
                                (ecase a
                                  (0 :q1)
                                  (1 :q1)))
                               (:q2
                                (ecase a
                                  (0 :q2)
                                  (1 :q1)))))
                         :q0 ;; initialize-instance state
                         '(:q1) ;; final state
                         '(1 1 1 1 1)))
;; a: 1 state: Q0
;; a: 1 state: Q0
;; a: 1 state: Q0
;; a: 1 state: Q0
;; a: 1 state: Q0
;; a: NIL state: Q0
NOT-ACCEPT
SECD> (run-dfa (make-dfa '(:q0 :q1 :q2) ;; states
                         '(0 1) ;; alphabet
                         #'(lambda (q a) ;; transition return new state
                             (ecase q
                               (:q0
                                (ecase a
                                  (0 :q2)
                                  (1 :q0)))
                               (:q1
                                (ecase a
                                  (0 :q1)
                                  (1 :q1)))
                               (:q2
                                (ecase a
                                  (0 :q2)
                                  (1 :q1)))))
                         :q0 ;; initialize-instance state
                         '(:q1) ;; final state
                         '(0 1 1 0 1)))
;; a: 0 state: Q2
;; a: 1 state: Q1
;; a: 1 state: Q1
;; a: 0 state: Q1
;; a: 1 state: Q1
;; a: NIL state: Q1
ACCEPT
SECD> 

０と１の出現がそれぞれ偶数回の文字列を受理するオートマトン。

最初の例は0が４個（偶数）、１が３個（奇数）なので受理されない。
後の例は0が４個、１が２個なので受理される。

SECD> (run-dfa (make-dfa '(:q0 :q1 :q2 :q3) ;; states
                         '(0 1) ;; alphabet
                         #'(lambda (q a) ;; transition return new state
                             (ecase q
                               (:q0
                                (ecase a
                                  (0 :q2)
                                  (1 :q1)))
                               (:q1
                                (ecase a
                                  (0 :q3)
                                  (1 :q0)))
                               (:q2
                                (ecase a
                                  (0 :q0)
                                  (1 :q3)))
                               (:q3
                                (ecase a
                                  (0 :q1)
                                  (1 :q2)))))
                         :q0 ;; initialize-instance state
                         '(:q0) ;; final state
                         '(0 0 1 1 0 0 1)))
;; a: 0 state: Q2
;; a: 0 state: Q0
;; a: 1 state: Q1
;; a: 1 state: Q0
;; a: 0 state: Q2
;; a: 0 state: Q0
;; a: 1 state: Q1
;; a: NIL state: Q1
NOT-ACCEPT
SECD> (run-dfa (make-dfa '(:q0 :q1 :q2 :q3) ;; states
                         '(0 1) ;; alphabet
                         #'(lambda (q a) ;; transition return new state
                             (ecase q
                               (:q0
                                (ecase a
                                  (0 :q2)
                                  (1 :q1)))
                               (:q1
                                (ecase a
                                  (0 :q3)
                                  (1 :q0)))
                               (:q2
                                (ecase a
                                  (0 :q0)
                                  (1 :q3)))
                               (:q3
                                (ecase a
                                  (0 :q1)
                                  (1 :q2)))))
                         :q0 ;; initialize-instance state
                         '(:q0) ;; final state
                         '(0 0 1 0 0 1)))
;; a: 0 state: Q2
;; a: 0 state: Q0
;; a: 1 state: Q1
;; a: 0 state: Q3
;; a: 0 state: Q1
;; a: 1 state: Q0
;; a: NIL state: Q0
ACCEPT
SECD> 

なるほど。