dfa から nfa へ

整理。

(defmethod convert-to-dfa ((fa nfa-e))
  (with-accessors ((alphabet alphabet-of)
                   (start start-state-of)
                   (accepts accept-states-of)) fa
    (let ((Dstates (make-hash-table :test #'equal))
          (Di (sort-states (epsilon-closure fa (list start))))
          (Dtable))
      (labels ((goto* (n-set a)
                 (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 (sort-states res))))
               (e-closure (s)
                 (sort-states (epsilon-closure fa s)))
               (find-not-marked (states)
                 (loop for s being the hash-keys in states
                    if (eql (gethash s states) 'not-marked)
                    return s))
               (mark-state (s states)
                 (setf (gethash s states) 'marked))
               (add-not-marked (s states)
                 (setf (gethash s states) 'not-marked)))
        ;; initialize
        (add-not-marked Di Dstates)
        ;; main
        (loop for s1 = (find-not-marked Dstates)
           while s1 do
             (mark-state s1 Dstates)
             (loop for a in alphabet
                for s2 = (e-closure (goto* s1 a)) do
                  (when (and s2 (null (gethash s2 Dstates)))
                    (add-not-marked s2 Dstates))
                  (setq Dtable (cons (list s1 a s2) Dtable))))
        ;; finalize
        (loop for s being the hash-keys in Dstates
           collect s into Dstates*
           collect
             `(,s
               ,@(loop for (s1 a s2) in Dtable
                    if (state= s s1)
                    collect `(,a ,s2))) into transit
           if (find-if #'(lambda (q) (member q accepts :test #'state=)) s)
           collect s into Daccepts
           finally
             (return (make-dfa Dstates* alphabet transit Di Daccepts)))))))

Dragon Book 図3.32 部分集合構成法、とかの疑似コードとかなり近いコードだ、という自画自賛。