04. 状態数を最小化する

03 章 で得た DFA は 5 状態だった。 このうち「どう入力を続けても受理・不受理の結果が変わらない」状態どうしは、区別する意味がない。 まとめてしまえば状態数が減る。

まず名前を短くする

集合のままでは読みにくいので、DFA を次のように書き直す。

書き直し前	書き直し後
(i)	i
(1,2,4)	1
(2,3,4)	2
(2,3,4,5)	3
(2,3,4,5,f)	f

ここから先の 1 2 3 は DFA の状態の名前であって、NFA の状態ではない。 02・03 章に出てきた 1 2 3 とは無関係なので注意。

遷移表は次のようになる。

状態	a による遷移先	b による遷移先
i	1	なし
1	2	3
2	2	3
3	2	f
f	2	f

1 と 2 の行が同じであることに気付く。これが最小化の手がかりになる。

手順

状態数最小化のアルゴリズム

1. DFA の状態を、最終状態からなる集合とそれ以外の集合の、2 つの集合に分ける
2. 各集合を遷移の種類によって分割する。
3. 各集合を、遷移先がどの集合に属するかによって分割する。
4. 上記 3 を繰り返して、どの集合もさらに分割できなくなったら終了。

「同じ集合に残ったものは区別がつかない」という状態から始めて、 違いが見つかるたびに分けていく。分けられなくなったら、残った集合が最小化後の状態である。

手で追う

上の遷移表に当てはめると、3 手で終わる。

手順	やること	分かれ方
(1)	最終状態とそれ以外に分ける	{f} / {i,1,2,3}
(2)	遷移の種類で分ける	{f} / {i} / {1,2,3}
(3)	遷移先の属する集合で分ける	{f} / {i} / {1,2} / {3}
(4)	もう分けられない	終了

(2) で i が外れるのは、i だけ b による遷移先を持たないからである。

(3) で 3 が外れるのは、b の行き先の属する集合が違うからである。 1 と 2 の b の行き先は 3 で、これは自分たちと同じ {1,2,3} の中にいる。 3 の b の行き先は f で、こちらは別の集合 {f} である。 a の行き先は 3 つとも 2、つまり同じ {1,2,3} の中なので、ここでは差が出ない。

比べるのは行き先の状態そのものではない。 同じ集合にいる状態はまだ区別がついていないのだから、 行き先が別の状態でも、その 2 つが同じ集合にいるなら行き先も区別がつかない。 この例では状態で比べても同じ答えになるが、一般にはそうならない。

残ったのは 4 つ。1 と 2 は最後まで分かれなかった。

最小化された DFA

残った 4 つの集合が、そのまま最小化された DFA の状態になる。 1 と 2 はまとめて 1,2 という 1 つの状態とする。

状態	a による遷移先	b による遷移先
i	1,2	なし
1,2	1,2	3
3	1,2	f
f（最終状態）	1,2	f

5 状態が 4 状態になった。図にすると次のようになる。

これも 03 章 の DFA の 2 条件を満たしたままである。 (1) ε の矢印が無い、(2) 1 つの丸から同じ記号の矢印が 2 本以上出ていない。

一致判定

03 章 で見た通り、あとは遷移表を 1 文字ずつ引くだけである。 ababb を判定してみる。

読んだ文字	今の状態
（最初）	i
a	1,2
b	3
a	1,2
b	3
b	f

読み終えたとき f にいるので受理。ababb は a(a|b)*bb に一致する。

ab なら読み終えた時点で 3 にいるので不受理。 bb は初めの b で i から行く先が無く、その場で不受理と決まる。

どの場合も、入力を 1 文字ずつ 1 回なぞるだけで済んでいる。

まとめ

章	入力	出力	状態数
02 章	正規表現 a(a\|b)*bb	NFA	7
03 章	NFA	DFA	5
04 章	DFA	最小化された DFA	4

正規表現から始めて、機械的な手続きだけで「1 文字ずつ表を引くだけ」の形まで辿り着いた。 途中に人間の工夫が要る箇所は 1 つもない。

ここまでは a(a|b)*bb という 1 つの例で手順を追ってきた。 05 章 からは、同じ手順をどのパターンにも効く形にする。 連接・|・( )・*、それに 02 章で予告した ? だけで書ける正規表現なら何でも、 内部で NFA を作り DFA に直して判定する——それを実装として組み立てていく。