DFA の最小化（区別可能な状態の対）

到達不能な状態を除き、区別可能な状態の対を表で順に印をつける方法（または同値類の分割の細分）で同値な状態をまとめ、与えられた DFA と同じ言語を受理する最小 DFA の状態数を求められる

前提

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）

説明

有限オートマトン（DFA）は、同じ言語を受理するものでも状態数がいろいろあります。この技能では、到達できない状態を取り除いたあと、「どんな入力を続けても受理・不受理の結果が変わらない」状態どうしを見つけてまとめます。こうして、同じ言語を受理する DFA のうち状態数が最も少ないもの（最小 DFA）とその状態数が求められます。回路やプログラムの状態機械を簡単にするとき、また 2 つの DFA が同じ言語を受理するかを調べるときに使います。

なぜそうしてよいのか

DFA を $M = (Q, Σ, δ, q_{0}, F)$ とします。 $δ^(p, w)$ は状態 $p$ から文字列 $w$ を読んだあとの状態です。2 つの状態 $p, q$ について、ある文字列 $w$ があって $δ^(p, w)$ と $δ^(q, w)$ のちょうど一方だけが受理状態になるとき、 $p, q$ は区別可能であるといいます。どんな $w$ （空文字列 $ε$ も含む）についても両方受理か両方不受理なら、 $p, q$ は同値であるといいます。同値な状態は、その先の振る舞いがまったく同じなので、1 つにまとめても受理する言語は変わりません。

区別可能な対は次の 2 つの規則で見つかります。(1) $w = ε$ のとき：一方が受理状態で他方が受理状態でなければ区別可能です。(2) ある文字 $x$ について $δ (p, x)$ と $δ (q, x)$ が文字列 $w$ で区別可能なら、 $p, q$ は $x w$ で区別可能です。逆に、区別可能な対 $p, q$ を区別する最短の文字列を $x w$ とすると、 $δ (p, x), δ (q, x)$ はより短い $w$ で区別されます。そのため、文字列の長さについての帰納法により、区別可能な対はすべていつかこの 2 規則で印がつきます。印がつかずに残った対がちょうど同値な対です。同値という関係は「 $p \sim q$ かつ $q \sim r$ なら $p \sim r$ 」を満たします。そのため、状態は同値なものどうしのグループ（同値類）に分かれます。また $p \sim q$ なら $δ (p, x) \sim δ (q, x)$ なので、まとめた後の遷移も矛盾なく決まります。

まとめた DFA が最小である理由は次のとおりです。まとめた後の状態が $k$ 個あり、どれも到達可能で、どの 2 つも区別可能だとします。各状態 $i$ に到達する文字列 $w_{i}$ を 1 つずつ選ぶと、 $i \neq = j$ に対して $w_{i} z$ と $w_{j} z$ の一方だけが受理される $z$ があります。同じ言語を受理する別の DFA が $w_{i}$ と $w_{j}$ を読んで同じ状態にいたとすると、続けて $z$ を読んでも同じ状態になり、矛盾します。よってどの DFA も少なくとも $k$ 個の状態を持ちます。到達不能な状態を先に除くのは、それらが受理言語に関係しないのに、残しておくと状態数が余計に数えられてしまうからです。

手順

到達不能な状態を除く：初期状態 $q_{0}$ から遷移をたどって行ける状態をすべて集め、行けない状態を捨てる。
残った状態のすべての対 ${p, q}$ の表を作る。一方だけが受理状態である対（ $p \in F, q \in / F$ など）に印をつける。
印のない各対 ${p, q}$ と各文字 $x$ について、行き先の対 ${δ (p, x), δ (q, x)}$ を調べる。それが印のついた対なら ${p, q}$ に印をつける（文字は 1 つで足りる。行き先が同じ状態なら、その文字では区別されない）。
手順 3 を表全体について繰り返し、1 周しても新しい印が 1 つも増えなくなったら止める。
最後まで印のない対は同値なので、同値な状態をまとめて同値類に分ける。同値類の個数が最小 DFA の状態数である（新しい遷移は、 $p$ を含む類から $δ (p, x)$ を含む類へとする）。

例題

アルファベット ${a, b}$ 上の DFA が次の遷移表で与えられている。初期状態は $A$ 、受理状態は $C$ のみである。

状態	$a$	$b$
$A$	$B$	$D$
$B$	$B$	$C$
$C$	$B$	$D$
$D$	$E$	$D$
$E$	$E$	$C$
$F$	$C$	$F$

この DFA と同じ言語を受理する最小 DFA の状態数を求めよ。

例題の解答

手順 1（到達不能な状態を除く）： $A$ から $B, D$ へ行けます。 $B$ から $C$ 、 $D$ から $E$ へ行けます。 $C, E$ からは新しい状態へ行けません。 $F$ へ入る遷移は $F$ 自身からしかないので、 $F$ は到達不能です。残りは ${A, B, C, D, E}$ で、対は $10$ 個です。

手順 2（初期の印）：受理状態は $C$ だけなので、 ${A, C}, {B, C}, {C, D}, {C, E}$ に印をつけます。

手順 3（1 周目）：
- ${A, B}$ ： $b$ で ${D, C}$ に行き、これは印あり。よって印をつける。
- ${A, D}$ ： $a$ で ${B, E}$ （印なし）、 $b$ で ${D, D}$ （同じ状態）。今は印をつけない。
- ${A, E}$ ： $b$ で ${D, C}$ に行き印あり。よって印をつける。
- ${B, D}$ ： $b$ で ${C, D}$ に行き印あり。よって印をつける。
- ${B, E}$ ： $a$ で ${B, E}$ （印なし）、 $b$ で ${C, C}$ （同じ状態）。今は印をつけない。
- ${D, E}$ ： $b$ で ${D, C}$ に行き印あり。よって印をつける。

手順 4（2 周目）：印のない対は ${A, D}$ と ${B, E}$ です。行き先は ${B, E}$ と ${D, D}$ 、 ${B, E}$ と ${C, C}$ で、どれも印がありません。新しい印は増えないので止めます。

手順 5（まとめる）：印のない対は ${A, D}, {B, E}$ なので、同値類は ${A, D}, {B, E}, {C}$ の 3 つです。したがって最小 DFA の状態数は $3$ です（この DFA は「 $ab$ で終わる文字列」を受理しています）。

答え: $3$

よくある誤り

到達不能な状態を除かずに表を作ってしまう誤り。例題で $F$ を残すと、 ${A, F}$ は $a$ で ${B, C}$ （印あり）へ行くなどして、 $F$ はどの状態とも区別されます。その結果、答えを $4$ としてしまいます。正しくは最初に $F$ を捨てて $3$ です。
手順 3 を 1 周しただけで止めてしまう誤り。ある周で新しくついた印が、次の周で別の対の印の根拠になることがあります。正しくは、1 周しても印が増えなくなるまで繰り返します。
受理状態どうし・非受理状態どうしをすべて同値としてしまう誤り。例題で ${A, B, D, E}$ を 1 つにまとめて $2$ 状態とするのは誤りです。正しくは ${A, B}$ は $δ (A, b) = D, δ (B, b) = C$ で区別可能です（ $A$ からは $b$ が不受理、 $B$ からは $b$ が受理）。
印をつける条件を取り違える誤り。すべての文字で行き先が印つきである必要はなく、ある 1 文字 $x$ で ${δ (p, x), δ (q, x)}$ が印つきなら十分です。また、行き先が同じ状態（例： ${A, D}$ の $b$ での行き先 ${D, D}$ ）は区別の根拠になりません。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

状態	入力 $a$	入力 $b$
$q_{0}$	$q_{1}$	$q_{3}$
$q_{1}$	$q_{4}$	$q_{2}$
$q_{2}$	$q_{2}$	$q_{2}$
$q_{3}$	$q_{1}$	$q_{0}$
$q_{4}$	$q_{1}$	$q_{2}$
$q_{5}$	$q_{2}$	$q_{0}$

状態	入力 $0$	入力 $1$
$A$	$D$	$B$
$B$	$E$	$C$
$C$	$C$	$D$
$D$	$A$	$E$
$E$	$B$	$C$
$F$	$A$	$F$

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$

この技能を使う問題

状態	$a$	$b$
$0$	${0, 1}$	${0}$
$1$	${2}$	${2, 3}$
$2$	${3}$	$\emptyset$
$3$	$\emptyset$	$\emptyset$

この技能の次に学べること

マイヒル・ネローデの定理と最小状態数（大学数学オートマトン・形式言語）

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$