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

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

1. 素朴な DFA。 $a$ の個数を 3 で割った余り $i\in \{0,1,2\}$ と、末尾の様子 $s\in \{N,A,B\}$（$A$: 最後の文字が $a$、$B$: 末尾が $ab$、$N$: それ以外（空文字列を含む））の組 $(i,s)$ を状態とする DFA が作れる。遷移は
- $a$ を読むと $(i,s)\to (i+1\mathrm{mod}3,A)$
- $b$ を読むと $(i,A)\to (i,B)$、$(i,B)\to (i,N)$、$(i,N)\to (i,N)$

で、初期状態 $(0,N)$、受理状態 $(0,B)$ である。9 状態すべてが到達可能だが、これは最小ではない。

2. 剰余言語の計算。 状態 $(i,s)$ にある文字列 $x$ のあとに $z$ を続けたとき、$xz\in L$ となる条件を調べる。
- $|z|\ge 2$ のとき：$xz$ が $ab$ で終わるかは $z$ だけで決まるので、条件は「$z$ が $ab$ で終わり、$i+|z{|}_a\equiv 0(\mathrm{mod}3)$」。これは $i$ だけで決まる。
- $z=a$ のとき：$xz$ は $a$ で終わるので常に $xz\notin L$。
- $z=b$ のとき：$xz\in L⟺s=A$ かつ $i\equiv 0$（$|z{|}_a=0$ だから）。
- $z=\epsilon$ のとき：$x\in L⟺s=B$ かつ $i\equiv 0$。

3. 同値類の決定。
- $i=1,2$ のとき、$z=b,\epsilon$ ではどの $s$ でも $xz\notin L$ であり、$|z|\ge 2$ の場合は $i$ だけで決まる。よって $(1,N),(1,A),(1,B)$ は互いに同値で 1 つの類、$(2,N),(2,A),(2,B)$ も 1 つの類になる。
- $i=0$ のとき、$(0,B)$ だけが $z=\epsilon$ を受理し、$(0,A)$ だけが $z=b$ を受理する。よって $(0,N),(0,A),(0,B)$ は互いに区別され、3 つの類になる。
- $i$ が異なる状態どうしは、$z=ab$（$i\equiv 2$ のときだけ受理）、$z=aab$（$i\equiv 1$ のときだけ受理）、$z=aaab$（$i\equiv 0$ のときだけ受理）で区別される。

以上より同値類は $3+1+1=5$ 個である。

4. 確認（5 状態の DFA）。 状態を $P_N,P_A,P_B,Q_1,Q_2$ とし、初期状態 $P_N$、受理状態 $P_B$、遷移を

とすると $L$ を受理し（例：$abaab$ は $P_N\to Q_1\to Q_1\to Q_2\to P_A\to P_B$ で受理）、すべての状態が到達可能である。

したがって最小 DFA の状態数は $5$ である。

まず積オートマトンを作る。$c\in \{0,1,2\}$ を $|w{|}_a\mathrm{mod}3$、$s\in \{0,1,2\}$ を末尾の状況（$s=1$: 最後の文字が $a$、$s=2$: $ab$ で終わる、$s=0$: それ以外（空列、または $a$ の直後でない $b$ で終わる））とする。遷移は $(c,s)\stackrel{a}{\to }(c+1,1)$、$(c,1)\stackrel{b}{\to }(c,2)$、$(c,0)\stackrel{b}{\to }(c,0)$、$(c,2)\stackrel{b}{\to }(c,0)$。初期状態 $(0,0)$、受理状態 $(0,2)$ のみ。9 状態すべて到達可能（例: $(c,1)$ は $a^c$ または $a^3$、$(c,2)$ は $a^{c}b$ または $aaab$、$(c,0)$ は $(c,2)$ から $b$）。

同値な状態をまとめる。
- $c\ne 0$ のとき、$(c,0),(c,1),(c,2)$ はいずれも非受理で、$a$ では $(c+1,1)$ に移り、$b$ では $(c,2)$ か $(c,0)$ に移る。これらは $c\ne 0$ なので非受理で、同じ振る舞いをする。よって $c=1$ の 3 状態は 1 つ（$A_1$）、$c=2$ の 3 状態は 1 つ（$A_2$）にまとまる。
- $c=0$ の $(0,0),(0,1),(0,2)$ は区別される。$(0,2)$ だけが受理状態。$(0,1)$ は $b$ で受理、$(0,0)$ は $b$ で受理しない。

簡約後の状態は $q_0=(0,0)$, $q_1=(0,1)$, $q_2=(0,2)$, $A_1$, $A_2$ の 5 個。

5 状態が互いに区別できること:
- $q_2$ は唯一の受理状態。
- $q_1$ は $b$ で受理、$q_0,A_1,A_2$ は $b$ で受理しない。
- $A_2$ は $ab$ で受理（$A_2\to q_1\to q_2$）。$q_0$ は $ab$ で $q_0\to A_1\to A_1$ で受理しない。$A_1$ も $A_1\to A_2\to A_2$ で受理しない。
- $q_0$ と $A_1$ は $aaab$ で区別: $q_0\to A_1\to A_2\to q_1\to q_2$（受理）、$A_1\to A_2\to q_1\to A_1\to A_1$（非受理）。

よって最小の DFA の状態数は 5。

検算: $aaab$: $q_0\to A_1\to A_2\to q_1\to q_2$ 受理。$abaab$: $q_0\to A_1\to A_1\to A_2\to q_1\to q_2$ 受理。$ab$: $q_0\to A_1\to A_1$ 非受理。$aaabb$: $q_2\to q_0$ 非受理。いずれも問題文の例と一致する。