makenowjust-labs/blog

前回の記事では DFA 最小化アルゴリズムとして Brzozowski のアルゴリズムを解説しました。 今回は、別の最小化アルゴリズムとして Hopcroft のアルゴリズムについて解説します。

"Introduction to Automata Theory, Languages, and Computation" (日本語訳『オートマトン 言語理論 計算論』) の著者の一人として知られる John Hopcroft が 1971 年に発表したアルゴリズムです。 実装を工夫することで最悪計算量は DFA の状態数 $n$ に対して $O(n \log n)$ となることが知られています。 しかし、正当さがやや直感的でないことから、オートマトン理論の教科書や講義などで触れられる機会は少ないように思います。

この記事では、Hopcroft のアルゴリズムの実装に加えて、その正しさの証明や計算量の解析を行います。

$A$ を言語 $L$ を受理する DFA とすると、$D(R(D(R(A))))$ は言語 $L$ を受理する最小 DFA となります。 ここで $D(A)$ というのは部分集合構成法による決定化の処理で、$R(A)$ は DFA の各遷移と初期状態・受理状態を反対にして NFA を求める処理を表します。 この 2 回のリバースと決定化を行う DFA の最小化アルゴリズムは Brozozowski のアルゴリズム として知られています。 Brzozowski 微分などで知られる Janusz Brzozowski が 1960 年代に発表したアルゴリズムです。

以前 Qiita でこのアルゴリズムでどうして DFA の最小化が行なえるのかを説明したのですが(Brzozowski のアルゴリズム - なぜ DFA を 2 回反転すると最小化できるのか )、これによって構成される DFA がどのようなものなのかは説明していませんでした。 今回のこの記事では、Brozozowski のアルゴリズムで求まる最小 DFA がどのようなものなのかを別の角度から少し解説したいと思います。