dfa から nfa 改良
さらに loop マクロを使ってみたけどあまり奇麗にはならないなぁ。
hashtable 使ってみたけど :test に equal を使っているのがいまいち気に入らない。
(defmethod convert-to-dfa ((fa nfa-e)) (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 res)))) (with-accessors ((alphabet alphabet-of) (start start-state-of) (accepts accept-states-of)) fa (let ((ht (make-hash-table :test #'equal))) (setf (gethash (epsilon-closure fa (list start)) ht) 'not-marked) (loop with Di = (epsilon-closure fa (list start)) with Dtable = nil with alphabet* = (loop for a in alphabet if a collect a) for s1 = (loop for k being the hash-keys in ht if (eql (gethash k ht) 'not-marked) return k) while s1 do (setf (gethash s1 ht) 'marked) (loop for a in alphabet* for s2 = (epsilon-closure fa (goto* s1 a)) do (when (and (not (null s2)) (null (gethash s2 ht))) (setf (gethash s2 ht) 'not-marked)) (setq Dtable (cons (list s1 a s2) Dtable))) finally (return (make-dfa (loop for s being the hash-keys in ht collect s) alphabet* (loop for s being the hash-keys in ht collect `(,s ,@(loop for (s1 a s2) in Dtable if (state= s s1) collect `(,a ,s2)))) Di (loop for s being the hash-keys in ht if (find-if #'(lambda (q) (member q accepts :test #'state=)) s) collect s))))))))