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

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

(1) 素朴な積オートマトン. 「$|w{|}_a\mathrm{mod}3$」を覚える 3 状態の DFA と、「$ab$ で終わるか」を判定する 3 状態の DFA（状態 $q_0$: $a$ でも $ab$ でも終わらない、$q_1$: $a$ で終わる、$q_2$: $ab$ で終わる）の積をとると、状態 $(r,q)$（$r\in \{0,1,2\}$, $q\in \{q_0,q_1,q_2\}$）の 9 状態の DFA が得られる。遷移は
$$(r,q)\stackrel{a}{\to }(r+1\mathrm{mod}3,q_1),(r,q_0)\stackrel{b}{\to }(r,q_0),(r,q_1)\stackrel{b}{\to }(r,q_2),(r,q_2)\stackrel{b}{\to }(r,q_0)$$
で、受理状態は $(0,q_2)$ のみである。9 状態はすべて到達可能である（例: $(r,q_1)$ には $a^{3k+r}$ の形で、$(r,q_2)$ には $a^r\cdots ab$ の形で、$(r,q_0)$ にはそれに $b$ を付けて到達できる。$r=0$ の場合は $aaa$, $aaab$, $aaabb$ や空列など）。

(2) $r\ne 0$ のときの同一視. $r\in \{1,2\}$ を固定し、$(r,q_0),(r,q_1),(r,q_2)$ を比べる。
- 記号 $a$ を読むと、3 つとも同じ状態 $(r+1\mathrm{mod}3,q_1)$ に移る。
- 記号 $b$ を読むと、$r$ は変わらず、移り先はそれぞれ $(r,q_0),(r,q_2),(r,q_0)$ で、ふたたびこの 3 つのどれかである。
- この 3 つはどれも受理状態ではない（$r\ne 0$）。

したがって、どの $z$ を読んでも、$z$ が $a$ を含めば最初の $a$ で同じ状態に合流し、$z$ が $a$ を含まなければ $r\ne 0$ のまま終わってすべて拒否される。よって $(r,q_0),(r,q_1),(r,q_2)$ は互いに区別できず、1 つにまとめられる。$r=1,2$ それぞれで 1 状態ずつになる。

(3) 残りの状態が区別できること. 残る状態は
$$P_1=\{r=1\},P_2=\{r=2\},(0,q_0),(0,q_1),(0,q_2)$$
の 5 つである。
- $r$ が異なるもの同士: $z=a^{k}ab$（$k\ge 0$）を読むと、受理されるのは $r+k+1\equiv 0(\mathrm{mod}3)$ のときだけである。$k$ を選べば $r$ の異なる 2 状態の一方だけを受理させられるので区別できる。たとえば $z=aab$ は $r=1$ からだけ受理、$z=aaab$ は $r=0$ からだけ受理される。
- $(0,q_2)$ と $(0,q_0)$, $(0,q_1)$: 空列 $z=\epsilon$ で $(0,q_2)$ だけが受理なので区別できる。
- $(0,q_1)$ と $(0,q_0)$: $z=b$ を読むと $(0,q_1)\to (0,q_2)$（受理）、$(0,q_0)\to (0,q_0)$（拒否）なので区別できる。

よって同値類はちょうど 5 個であり、具体的には
- $|w{|}_a\equiv 1$、$|w{|}_a\equiv 2(\mathrm{mod}3)$ の 2 類
- $|w{|}_a\equiv 0$ で、$ab$ で終わる／$a$ で終わる／それ以外 の 3 類

である。最小 DFA の状態数は $5$ である。

答え: $5$

まず、a の個数を 3 で割った余り $c\in \{0,1,2\}$ と、末尾の状況 $s$ を組にした DFA を作る。$s$ は次の 3 通りとする。$A$ は直前の文字が a、$AB$ は末尾が ab、$N$ はそれ以外（空列、または末尾が b で、その直前が a でない）である。

遷移は次のとおり。a を読むと $(c,s)\to (c+1\mathrm{mod}3,A)$。b を読むと、$s=A$ なら $(c,AB)$、$s=AB$ または $N$ なら $(c,N)$。初期状態は $(0,N)$、受理状態は $(0,AB)$ のみ。9 個の状態はすべて到達可能である（$(c,A)$ は a を $c$ 回読んで、$(c,AB)$ はそのあと b を読んで、$(c,N)$ はさらに b を読んで到達できる）。

最小化する。

1. $c=1,2$ では受理状態がなく、$(c,N)$、$(c,AB)$、$(c,A)$ はどれも a で $(c+1,A)$ へ、b で $(c,N)$ または $(c,AB)$ へ進む。この 2 つは $c\ne 0$ では同値なので、3 つの状態は 1 つにまとまる。これを $Q_1,Q_2$ とする。遷移は $Q_1\stackrel{a}{\to }{Q}_2$、$Q_2\stackrel{a}{\to }(0,A)$、$Q_c\stackrel{b}{\to }{Q}_c$ となる。
2. $c=0$ では $(0,N),(0,AB),(0,A)$ の 3 つが残る。$(0,AB)$ だけが受理状態。$(0,N)$ と $(0,A)$ は、b を読むと一方は $(0,N)$ で非受理、他方は $(0,AB)$ で受理となり区別される。
3. 残る 5 状態 $(0,N),(0,AB),(0,A),Q_1,Q_2$ が互いに区別できることを示す。
- $(0,AB)$ は唯一の受理状態なので、空列で他と区別される。
- $(0,A)$ は b で受理するが、$(0,N),Q_1,Q_2$ は b で受理しない。
- $Q_2$ は ab で受理する（$Q_2\to (0,A)\to (0,AB)$）が、$(0,N)$ と $Q_1$ は ab で受理しない（$Q_1$ は $Q_2$ に行って $Q_2$ にとどまる）。
- $(0,N)$ は aaab で受理するが、$Q_1$ は aaab で受理しない（$Q_1\to Q_2\to (0,A)\to Q_1\to Q_1$）。

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

検算として、$w=ab$ ($|w{|}_a=1$) は拒否、$aaab$ は $(0,N)\to Q_1\to Q_2\to (0,A)\to (0,AB)$ で受理（a が 3 個で ab で終わる）、$ababab$ は a が 3 個で ab で終わるので受理され、5 状態で正しく動く。