読者です 読者をやめる 読者になる 読者になる

DFAの簡略化

計算理論

第一部の最後。任意のDFAから、それと等価で状態数が最小のDFAを求める手法。計算機の設計とかで使われるので、重要。

  • 状態数が少ないとハードウェアが小さくできる
  • 情報検索
    • 正則表現のような検索をしたいとき(DFAみたいなものを中で作っているらしい)
    • なんか似たようなのをIIRで見た気がするぞ

まず、定理9.1で「各同値類を1つの状態として作られるDFAは、状態数が最小である」ということが与えられる。なので、どうやって同値類を求めていくかということについて考えていく。

同値の条件を緩めたk-同値類というものを考える。そっから先は数学的帰納法を使って示される。つまり

  • 0-同値類について成立することを確認
  • n-1同値類について成立すると仮定して、n同値類について成立

ということを示す。今考えているのは状態数が高々有限なものである。それゆえ、k-同値類で条件を緩めていったものを考えていたが、帰納法を繰替えしていけば、もとのものが示せるということになる。

実際に動かしていくアルゴリズム自体は簡単。手を動かすだけで頭は動かさなくてよい。