決定性有限オートマトンの状態数の最小化

同じ遷移をする状態を同一視し、冗長な状態数をまとめて状態数を最小化する

NFAからDFAへの変換の続きでもある

↑この作業でDFAにするのをミスってたら以降間違い続ける

(a|b)^\ast ab(a|b)^\ast cの正規表現をDFAにしたものを考える

これが↓NFAから考えたDFA。これを最小化をする

①上のノードを新たに名前を振る

②表を作る

③この表をある規則によってわけていく(行方向に見る)

まず「最終状態かどうか」でわける

今回は 7 のみが最終状態なのでなので\{1,2,3,4,5,6\}、\{7\}になる

④上で分けた2つの集合に対して以下のことをして分類していく

行がの内容が一致するもので分類する

遷移先と遷移の種類が一致するものを見ている

なお、今回は最終状態である方の集合は 7 のみなので、こっちの集合に関してはこれ以上分割されない

なので、前者の方を見ていく

「これ」同士と、「コレ」同士が全くおなじになっているのがわかる

同じもの同士を結合する

(これ) 1 と 5 を合体して新しく 8 とする

(コレ) 3 と 4 と 6 を合体して新しく 9 としよう

こうなる

対応表の中にまだ 4 とか 5 とかが残っているので 8 や 9 に書き換える

④この操作を繰り返し、これ以上分割できなくなるまでやる

今回はこれで終わり

⑤最後に表を参考にしてDFAの図を作る