SLIME(The Superior Lisp Interaction Mode for Emacs) の REPL バッファに画像を表示できることがわかった。この機能はなかなか応用が利きそうだ。 SLIME の準備 以下必要な準備。 SLIME を環境を最新にする conrib/slime-media.el をロードする eval-in-em…

DFA の状態数の最小化について、"Brzozowski のアルゴリズム"なる方法があるらしい。Dragon Book アルゴリズム 3.39 とは違うアプローチで、二回 reverse して二回 部分集合構成法を適用するだけ、というものだ。まだ実装できていないが、このアルゴリズムで…

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 re…

整理。 (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)))…

さらに loop マクロを使ってみたけどあまり奇麗にはならないなぁ。 hashtable 使ってみたけど :test に equal を使っているのがいまいち気に入らない。 (defmethod convert-to-dfa ((fa nfa-e)) (labels ((goto* (n-set a) (loop for s in n-set with res = …

メモ。 subset construction を教科書のアルゴリズムに習って実装したもの。まだ汚いコードだ。疑似コードをそのままプログラムに落とせるようにしておいて、この次の dfa の状態数の最小化に備える。 not-marked とかやっている辺りがあまりにもどんくさい…