2017-04-21から1日間の記事一覧

Hopcroft 法で DFA 最小化

DFA の最小化の代表的なアルゴリズムは Hopcroft 法です。 終状態とそうでない状態に 2 分割しておいてから、 さらに分割を進めていくのは Moore 法と同じですが、 再試行なしで幅優先で分割を進めていくため、 理論上の最悪計算量はΟ(n log n) です。 とい…