DFA から NFA へ

メモ。
subset construction を教科書のアルゴリズムに習って実装したもの。まだ汚いコードだ。

疑似コードをそのままプログラムに落とせるようにしておいて、この次の dfa の状態数の最小化に備える。
not-marked  とかやっている辺りがあまりにもどんくさい。もっとエレガントにしなくては。

(defmethod convert-to-dfa ((fa nfa-e))
  (labels ((goto* (n-set a)
             ;; (format t ";; n-set: ~a" n-set)
             (loop for s in n-set with res = ()
                do (loop for q in (transit fa s a)
                      do (pushnew q res :test #'state=))
                finally (return res))))
    (with-accessors ((alphabet alphabet-of)
                     (start start-state-of)
                     (accepts accept-states-of)) fa
      (let* ((Di (epsilon-closure fa (list start)))
             (Dstates (list (cons Di 'not-marked))) ;; ex. ((q0 a1) . not-marked)
             (Dtable) ;; ((s a s2) ...)
             (s1)
             (alphabet* (loop for a in alphabet if a collect a)))
        ;; (format t ";; Di: ~a~%" Di)
        (loop
           (setq s1 (car (find-if #'(lambda (x)
                                      (and (consp x)
                                           (eql (cdr x) 'not-marked))) Dstates)))
           ;; (format t ";; check s1: ~a~%" s1)
           (unless s1
             (return (values Di Dstates)))
           ;; mark s1
           ;; (format t ";; mark s1(~a)...~%" s1)
           (setq Dstates (acons s1 'marked (remove s1 Dstates :key #'car :test #'state=)))
           ;; (format t ";; mark s1: ~a~%" s1)
           ;; (format t ";; Dstates: ~a~%" Dstates)
           (loop for a in alphabet* do
              ;; (format t ";; loop for a: ~a~%" a)
                (let ((s2 (epsilon-closure fa (goto* s1 a))))
                  ;; (format t ";; s2: ~a~%" s2)
                  (when (and (not (null s2))
                             (not (member s2 Dstates :key #'car :test #'state= )))
                    ;; (format t ";; if s2 is not nil ~%")
                    (setq Dstates (acons s2 'not-marked Dstates)))
                  ;; (format t ";; append s2 to Dtable: s2: ~a~%" s2)
                  (setq Dtable (cons (list s1 a :=> s2) Dtable)))))
        ;; (format t ";; Dstates:~%~a" Dstates)
        ;; (format t ";; Dtable:~%~a" Dtable)
        (let ((Dstates* (loop for (s . nil) in Dstates collect s)))
          (make-dfa Dstates* alphabet*
                    (loop for s in Dstates*
                       collect `(,s
                                 ,@(loop for (s1 a nil s2) in Dtable
                                      if (state= s s1)
                                      collect `(,a ,s2))))
                    Di
                    (loop for s in Dstates*
                       if (find-if #'(lambda (q)
                                       (member q accepts :test #'state=)) s)
                       collect s)))
        ))))