DFA から NFAへ

メモ。
Wikipedia http://en.wikipedia.org/wiki/Powerset_construction の Example 2 より。
まだ到達不能な状態を除去していないので冗長。

FA> (let ((nfa (def-nfa '(:a :b :c)
                   '(0 1)
                 ((:a
                   (0 nil)
                   (1 '(:b :c)))
                  (:b
                   (0 '(:a))
                   (1 nil))
                  (:c
                   (0 '(:b))
                   (1 nil))) :a '(:c))))
      (print nfa)
      (convert-to-dfa nfa))

#<NFA:
  Q  = {A B C}
  F  = {C}
  q0 = A
  Σ  = {0 1}
  δ  = 
  state       0           1           
  ====================================
> A           NIL         (B C)       
  B           (A)         NIL         
 *C           (B)         NIL         
> 
#<DFA:
  Q  = {(A B C) (A B) (A C) (A) (B C) (B) (C) NIL}
  F  = {(A B C) (A C) (B C) (C)}
  q0 = (A)
  Σ  = {0 1}
  δ  = 
  state       0           1           
  ====================================
 *(A B C)     (A B)       (B C)       
  (A B)       (A)         (B C)       
 *(A C)       (B)         (B C)       
> (A)         NIL         (B C)       
 *(B C)       (A B)       NIL         
  (B)         (A)         NIL         
 *(C)         (B)         NIL         
  NIL         NIL         NIL         
>
FA> 

変換関数は定義通りに以下のように書ける。まだテストが足りないけど。

(defmethod convert-to-dfa ((nfa nfa))
  (with-accessors ((q-n set-of-states-of)
                   (alphabet alphabet-of)
                   (delta-n transition-function-of)
                   (start-state start-state-of)
                   (f-n set-of-accept-states-of)) nfa
    (let* ((q-d (power-set q-n))
           (f-d (loop for s in q-d
                   if (some #'(lambda (q) (member q f-n :test #'state=)) s)
                   collect s))
           (transition-function #'(lambda (s symbol)
                                    (loop for q in s
                                       append (transit nfa q symbol)))))
      (make-dfa q-d alphabet transition-function (list start-state) f-d))))

このあと

• 到達不能な状態の除去
• ε遷移のある nfa とその除去

など。