Brzozowski のアルゴリズム
DFA の状態数の最小化について、"Brzozowski のアルゴリズム"なる方法があるらしい。Dragon Book アルゴリズム 3.39 とは違うアプローチで、二回 reverse して二回 部分集合構成法を適用するだけ、というものだ。まだ実装できていないが、このアルゴリズムで NFA を最小の DFA に変換するコードは以下のようになる。
(defmethod minimize ((nfa nfa)) (rename-states (reachable (subset (reverse-fa (rename-states (reachable (subset (reverse-fa nfa)))))))))
なぜこれでうまくいくのか、今は全く理解できない。
続く。