dfa から nfa setf + loop initially
setf とループを組み合わせてより簡潔に。initially という loop キーワードを初めて使った。
(defmethod convert-to-dfa ((nfa nfa)) (labels ((goto* (n-set a) (loop for s in n-set with res = () do (loop for q in (transit nfa s a) do (pushnew q res :test #'state=)) finally (return (sort-states res)))) (e-closure (s) (sort-states (epsilon-closure nfa s))) (find-unmark (states) (loop for s being the hash-keys in states if (eql (gethash s states) 'unmark) return s)) (mark (s states mark) (setf (gethash s states) mark))) ;; main (loop initially (mark (start-state-of dfa) Dstates 'unmark) with dfa = (make-instance 'dfa :accept nil :alphabet (alphabet-of nfa) :start (sort-states (epsilon-closure nfa (list (start-state-of nfa)))) :states nil) with Dstates = (make-hash-table :test #'equal) for s1 = (find-unmark Dstates) while s1 do (mark s1 Dstates t) (push s1 (states-of dfa)) (when (find-if #'(lambda (q) (member q (accept-states-of nfa) :test #'state=)) s1) (push s1 (accept-states-of dfa))) (loop for a in (alphabet-of dfa) for s2 = (e-closure (goto* s1 a)) do (when (and s2 (null (gethash s2 Dstates))) (mark s2 Dstates 'unmark)) (setf (transit dfa s1 a) s2)) finally (return dfa))))