メモ Brzozowski のアルゴリズム

元論文が入手できればたぶん一発で理解できるのだが、メモ。

• reverse - subset - reverse - subset の操作で NFA を最小化するアルゴリズム。
• NFA を反転させる操作 reverse は、オートマトンを図示した場合、すべての矢印の向きを反転させ、開始状態と終了状態を入れ替える操作である。
• 元の NFA が複数の終了状態を持つ場合、reverse した NFA は複数の開始状態があることになる。
• NFA に複数の開始状態は許されないと思っていたので、開始状態が複数生じた場合、その状態へε遷移する状態を勝手に追加してそれを開始状態としていた。わたしの勘違い。
• NFA に複数の開始状態があっても、問題はない - subset 構成法で DFA にすればどうせ併合されるので。（たぶん）

敗因は数式をちゃんと追っていなかったこと、原著論文にあたらなかったこと、そして例をちゃんと検証しなかったこと。
「例示は理解の試金石」か。ちきしょう。