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

マイヒル・ネローデの定理より、最小の完全 DFA の状態数は、次の同値関係 ${\equiv }_L$ の同値類の個数に等しい。
$$x{\equiv }_{L}y⟺\text{すべての }z\in {\Sigma }^{\ast }\text{ について }(xz\in L\iff yz\in L)$$

手順 1：同値類が高々 4 個であることを示す。
文字列 $x$ の前に $bb$ を付けた $bbx$ の最後の 2 文字を $x$ の「末尾 2 文字」と呼ぶ（$x=\epsilon$ なら $bb$、$x=a$ なら $ba$、$x=b$ なら $bb$）。接尾辞 $z$ を付けたとき $xz\in L$ となるかは、次のように決まる。
- $|z|\ge 2$ のとき：$xz$ の後ろから 2 番目の文字は $z$ の後ろから 2 番目の文字なので、$x$ によらない。
- $|z|=1$ のとき：$xz$ の後ろから 2 番目の文字は $x$ の最後の文字。$x=\epsilon$ なら $|xz|=1$ で $L$ に属さないが、これは末尾 2 文字 $bb$ の最後の文字 $b$ の場合と同じ結果になる。
- $z=\epsilon$ のとき：$x$ の後ろから 2 番目の文字が $a$ かどうか。$|x|\le 1$ なら $x\notin L$ で、これも末尾 2 文字の 1 文字目が $b$ の場合と同じ結果になる。

よって、末尾 2 文字が等しい $x,y$ はすべての $z$ で同じ結果になり、$x{\equiv }_{L}y$ である。末尾 2 文字は $aa,ab,ba,bb$ の 4 通りなので、同値類は高々 4 個である。

手順 2：代表元 $aa,ab,ba,bb$ が互いに区別できることを示す。
- $z=\epsilon$ とする。$aa,ab\in L$、$ba,bb\notin L$ である。よって $\{aa,ab\}$ の元と $\{ba,bb\}$ の元は区別できる（4 組）。
- $aa$ と $ab$：$z=a$ とすると、$aaa\in L$（後ろから 2 番目が $a$）、$aba\notin L$（後ろから 2 番目が $b$）である。
- $ba$ と $bb$：$z=a$ とすると、$baa\in L$、$bba\notin L$ である。

これで $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 組すべてが区別できた。よって同値類はちょうど 4 個ある。

結論： マイヒル・ネローデの定理より、最小の完全 DFA の状態数は $4$ である。

$|w|\ge 2$ は「後ろから 2 番目の文字が $a$」から自動的に従うので、$L$ は「後ろから 2 番目の文字が $a$」の言語と同じである。

【DFA の構成】
状態を「直近 2 文字」とし、$w$ が 2 文字未満のときは先頭を $b$ で補う。状態は $q_{xy}$ ($x,y\in \{a,b\}$) の 4 個。
- 初期状態: $q_{bb}$（空語 $\epsilon$ に対応）
- 受理状態: $q_{aa},q_{ab}$（後ろから 2 番目が $a$）
- 遷移: $\delta (q_{xy},c)=q_{yc}$

この DFA が $L$ を受理することは、状態が常に直近 2 文字（不足分は $b$ で補う）を表すことから従う。補った $b$ は先頭の $a$ にはならないので、長さ 1 以下の語は正しく棄却される。

【最小性】4 状態がすべて区別可能であることを示す。
- 受理状態 $\{q_{aa},q_{ab}\}$ と非受理状態 $\{q_{ba},q_{bb}\}$ は、空語 $\epsilon$ で区別できる。
- $q_{aa}$ と $q_{ab}$ は、続けて $a$ を読むと $q_{aa}$（受理）と $q_{ba}$（非受理）になるので区別できる。
- $q_{ba}$ と $q_{bb}$ は、続けて $a$ を読むと $q_{aa}$（受理）と $q_{ba}$（非受理）になるので区別できる。

よって 4 状態はすべて互いに区別でき、これ以上減らせない。到達可能性も、$bb\to a\to ba\to a\to aa\to b\to ab$ により全状態で確かめられる。

【検算】$ab$: $bb\to ba\to ab$（受理）。$aba$: $bb\to ba\to ab\to ba$（非受理）。$baa$: $bb\to bb\to ba\to aa$（受理）。いずれも問題文の例と一致する。

答え: 4