makenowjust-labs/blog

$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 がどのようなものなのかを別の角度から少し解説したいと思います。