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)))))))))

なぜこれでうまくいくのか、今は全く理解できない。

続く。