DFAの状態数の最小化
同じ遷移をする状態を同一視し、冗長な状態数をまとめて状態数を最小化する
↑この作業でDFAにするのをミスってたら以降間違い続ける
$ (a|b)^\ast ab(a|b)^\ast cの正規表現をDFAにしたものを考える
これが↓NFAから考えたDFA。これを最小化をする
https://gyazo.com/9916898cd0b892f81c14e40283dae423
①上のノードを新たに名前を振る
https://gyazo.com/f28227f6106190e5365fcb8e4720ab0c
②表を作る
table:対応表
a b c
1 2 5 x
2 2 3 x
3 4 6 7
4 4 6 7
5 2 5 x
6 4 6 7
7 x x x
③この表をある規則によってわけていく(行方向に見る)
まず「最終状態かどうか」でわける
今回は7のみが最終状態なのでなので$ \{1,2,3,4,5,6\}、$ \{7\}になる
④上で分けた2つの集合に対して以下のことをして分類していく
行がの内容が一致するもので分類する
遷移先と遷移の種類が一致するものを見ている
なお、今回は最終状態である方の集合は7のみなので、こっちの集合に関してはこれ以上分割されない
なので、前者の方を見ていく
table:対応表
a b c
1 2 5 x ←コレ
2 2 3 x
3 4 6 7 ←これ
4 4 6 7 ←これ
5 2 5 x ←コレ
6 4 6 7 ←これ
「これ」同士と、「コレ」同士が全くおなじになっているのがわかる
同じもの同士を結合する
(これ)1と5を合体して新しく8とする
(コレ)3と4と6を合体して新しく9としよう
こうなる
table:対応表
a b c
2 2 3 x
8 2 5 x
9 4 6 7
対応表の中にまだ4とか5とかが残っているので8や9に書き換える
table:対応表の
a b c
2 2 9 x
8 2 8 x
9 9 9 7
④この操作を繰り返し、これ以上分割できなくなるまでやる
今回はこれで終わり
⑤最後に表を参考にしてDFAの図を作る
https://gyazo.com/97af287436d1575b3f34712c1ebd085a