オートマトン・形式言語の問題

部分集合構成. 初期状態 $\{0\}$ から到達できる部分集合だけを順に作る。状態 $0$ は $a,b$ どちらでも $0$ に戻るので、到達する部分集合はすべて $0$ を含み、空集合は現れない。

• $\{0\}$: $a\to \{0,1\}$, $b\to \{0\}$
• $\{0,1\}$: $a\to \{0,1\}\cup \{2\}=\{0,1,2\}$, $b\to \{0\}\cup \{2,3\}=\{0,2,3\}$
• $\{0,1,2\}$: $a\to \{0,1\}\cup \{2\}\cup \{3\}=\{0,1,2,3\}$, $b\to \{0\}\cup \{2,3\}\cup \varnothing =\{0,2,3\}$
• $\{0,2,3\}$: $a\to \{0,1\}\cup \{3\}\cup \varnothing =\{0,1,3\}$, $b\to \{0\}$
• $\{0,1,2,3\}$: $a\to \{0,1,2,3\}$, $b\to \{0,2,3\}$
• $\{0,1,3\}$: $a\to \{0,1,2\}$, $b\to \{0,2,3\}$

新しい部分集合はもう現れないので、到達可能な状態は 6 個である。
$A=\{0\},B=\{0,1\},C=\{0,1,2\},D=\{0,2,3\},E=\{0,1,2,3\},F=\{0,1,3\}$ とおくと、遷移は

であり、$2$ または $3$ を含む $C,D,E,F$ が受理状態、$A,B$ が非受理状態である。この DFA はすべての状態が初期状態から到達可能である。

最小化（同値な状態の併合）. 受理・非受理で分けた分割 $\{A,B\},\{C,D,E,F\}$ から始め、各状態の遷移先がどのブロックに入るかで細分する。

• $\{A,B\}$: $A$ の遷移先 $(B,A)$ は (非受理, 非受理)、$B$ の遷移先 $(C,D)$ は (受理, 受理)。よって $\{A\},\{B\}$ に分かれる。
• $\{C,D,E,F\}$: $C\to (E,D)$, $E\to (E,D)$, $F\to (C,D)$ はいずれも (受理, 受理) だが、$D\to (F,A)$ は (受理, 非受理)。よって $\{C,E,F\},\{D\}$ に分かれる。

分割 $\{A\},\{B\},\{C,E,F\},\{D\}$ で再び調べると、$C,E,F$ はいずれも $a$ で $\{C,E,F\}$ に、$b$ で $\{D\}$ に移るので、これ以上分かれない。よって分割は安定し、同値類は 4 個である。

（実際、$L(N)={\Sigma }^{\ast }(aa+ab+aba)$ であり、4 つの同値類はそれぞれ「末尾が $a$ でも受理でもない列（$\{A\}$）」「受理でない、末尾が $a$ の列（$\{B\}$）」「末尾が $aa$ または $aba$ の列（$\{C,E,F\}$）」「末尾が $ab$ の列（$\{D\}$）」に対応する。たとえば $A$ と $B$ は文字列 $a$ で、$D$ と $\{C,E,F\}$ は文字列 $b$ で区別される。）

到達不能な状態がなく、同値な状態をすべて併合した DFA は最小 DFA なので、求める状態数は $4$ である。

部分集合構成で DFA にする。$\delta (0,a)=\{0,1\}$, $\delta (0,b)=\{0\}$ から始める。

到達可能な状態: $A=\{0\}$, $B=\{0,1\}$, $C=\{0,1,2\}$, $D=\{0,2,3\}$, $E=\{0,1,2,3\}$, $F=\{0,1,3\}$。

遷移:
- $A$: $a\to B$, $b\to A$
- $B$: $a\to \{0,1\}\cup \{2\}=C$, $b\to \{0\}\cup \{2,3\}=D$
- $C$: $a\to \{0,1\}\cup \{2\}\cup \{3\}=E$, $b\to \{0\}\cup \{2,3\}=D$
- $D$: $a\to \{0,1\}\cup \{3\}=F$, $b\to \{0\}=A$
- $E$: $a\to E$, $b\to D$
- $F$: $a\to \{0,1\}\cup \{2\}=C$, $b\to \{0\}\cup \{2,3\}=D$

受理状態は 2 または 3 を含む $C,D,E,F$。非受理は $A,B$。

最小化（分割の細分）:
- 初期分割 $\{A,B\}$, $\{C,D,E,F\}$。
- $A$ は $a\to B$, $b\to A$（ともに非受理）、$B$ は $a\to C$, $b\to D$（ともに受理）なので $A$ と $B$ は区別される。
- $D$ は $b\to A$（非受理）だが、$C,E,F$ は $b\to D$（受理）なので $D$ は区別される。
- $C,E,F$ は $a$ で $E,E,C$、$b$ で $D,D,D$ に行き、いずれも $\{C,E,F\}$ または $D$ に入るので同値。

最終分割 $\{A\},\{B\},\{D\},\{C,E,F\}$ で 4 状態。これ以上は分割できないので最小。

検算: $L(N)$ は「最後から 3 番目が $a$、または最後から 2 番目が $a$ かつ…」のように直近の文字に依存する言語で、$a$ の直前 3 文字の履歴を区別する 4 状態で表せる。例えば $b$ 列後の $a$ で $B$、そこから $a$ なら $C$ 群（受理）、$b$ なら $D$（受理）と、NFA の受理と一致する。