syou6162
https://blog.hatena.ne.jp/syou6162/
yasuhisa's blog
https://www.yasuhisay.info/
計算理論
第一部の最後。任意のDFAから、それと等価で状態数が最小のDFAを求める手法。計算機の設計とかで使われるので、重要。 状態数が少ないとハードウェアが小さくできる 情報検索 正則表現のような検索をしたいとき(DFAみたいなものを中で作っているらしい) なんか似たようなのをIIRで見た気がするぞ まず、定理9.1で「各同値類を1つの状態として作られるDFAは、状態数が最小である」ということが与えられる。なので、どうやって同値類を求めていくかということについて考えていく。同値の条件を緩めたk-同値類というものを考える。そっから先は数学的帰納法を使って示される。つまり 0-同値類について成立することを…
190
<iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwww.yasuhisay.info%2Fentry%2F20100426%2F1272241016" title="DFAの簡略化 - yasuhisa's blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe>
Hatena Blog
https://hatena.blog
2010-04-26 09:16:56
DFAの簡略化
rich
https://www.yasuhisay.info/entry/20100426/1272241016
1.0
100%