第一部の最後。任意のDFAから、それと等価で状態数が最小のDFAを求める手法。計算機の設計とかで使われるので、重要。
- 状態数が少ないとハードウェアが小さくできる
- 情報検索
- 正則表現のような検索をしたいとき(DFAみたいなものを中で作っているらしい)
- なんか似たようなのをIIRで見た気がするぞ
まず、定理9.1で「各同値類を1つの状態として作られるDFAは、状態数が最小である」ということが与えられる。なので、どうやって同値類を求めていくかということについて考えていく。
同値の条件を緩めたk-同値類というものを考える。そっから先は数学的帰納法を使って示される。つまり
- 0-同値類について成立することを確認
- n-1同値類について成立すると仮定して、n同値類について成立
ということを示す。今考えているのは状態数が高々有限なものである。それゆえ、k-同値類で条件を緩めていったものを考えていたが、帰納法を繰替えしていけば、もとのものが示せるということになる。
実際に動かしていくアルゴリズム自体は簡単。手を動かすだけで頭は動かさなくてよい。
