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))) ))))