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

方針　まず $\mathrm{val}(w)$ を $24$ で割った余りを状態とする DFA を作り、マイヒル・ネローデの定理に基づいて、どの余りどうしが区別できるかを調べる。

余りの DFA　文字列 $w$ の後ろに長さ $k$ の文字列 $z$ をつなぐと
$$\mathrm{val}(wz)=2^k\mathrm{val}(w)+\mathrm{val}(z)$$
となる。したがって $wz\in L$ かどうかは $r=\mathrm{val}(w)\mathrm{mod}24$ と $z$ だけで決まり、状態 $r\in \{0,1,\dots ,23\}$、遷移 $\delta (r,c)=2r+c\mathrm{mod}24$、初期状態 $0$、受理状態 $\{0\}$ の DFA が $L$ を受理する。どの $r$ も値が $r$ の文字列で到達できるので、24 状態はすべて到達可能である。最小 DFA の状態数は、この 24 個の余りを「同値（どんな $z$ をつないでも受理・非受理が一致する）」で分けたときの類の数に等しい。

受理条件の分解　$z$ の長さを $k$、$v=\mathrm{val}(z)$（$0\le v\le 2^k-1$）とする。$24=8\cdot 3$ で $8$ と $3$ は互いに素だから
$$2^{k}r+v\equiv 0(\mathrm{mod}24)⟺2^{k}r+v\equiv 0(\mathrm{mod}8)\text{かつ}{2}^{k}r+v\equiv 0(\mathrm{mod}3).$$

• $k\ge 3$ のとき：$2^{k}r\equiv 0(\mathrm{mod}8)$ なので、mod 8 の条件は $v\equiv 0(\mathrm{mod}8)$ となり $r$ によらない。mod 3 の条件は $r\mathrm{mod}3$ だけで決まる。よって受理は $r\mathrm{mod}3$ だけで決まる。
• $k=0$（$z=\epsilon$, $v=0$）のとき：受理 $⟺r\equiv 0(\mathrm{mod}24)$、すなわち $r=0$。
• $k=1$ のとき：$v\in \{0,1\}$ で、$2r+v\equiv 0(\mathrm{mod}8)$ には $v$ が偶数、つまり $v=0$ が必要。このとき条件は $2r\equiv 0(\mathrm{mod}8)$ かつ $2r\equiv 0(\mathrm{mod}3)$、すなわち $r\equiv 0(\mathrm{mod}4)$ かつ $r\equiv 0(\mathrm{mod}3)$。
• $k=2$ のとき：$v\in \{0,1,2,3\}$ で、$4r+v\equiv 0(\mathrm{mod}8)$ には $v\equiv 0(\mathrm{mod}4)$、つまり $v=0$ が必要。このとき条件は $r\equiv 0(\mathrm{mod}2)$ かつ $r\equiv 0(\mathrm{mod}3)$。

特に $k\le 2$ では $r\equiv 0(\mathrm{mod}3)$ でなければ決して受理しない。

同値類　以上から、$r\mathrm{mod}3$ と、$r\equiv 0(\mathrm{mod}3)$ のときは「$r$ が $8$・$4$・$2$ で割り切れるか」が受理を決める。

• $r\equiv 1(\mathrm{mod}3)$ の 8 個：$k\le 2$ では常に非受理、$k\ge 3$ では $r\mathrm{mod}3$ だけで決まるので、すべて同値で 1 類。
• $r\equiv 2(\mathrm{mod}3)$ の 8 個：同様に 1 類。
• $r\equiv 0(\mathrm{mod}3)$ の 8 個 $\{0,3,6,9,12,15,18,21\}$：
• $8$ で割り切れる：$\{0\}$
• $4$ で割り切れるが $8$ では割り切れない：$\{12\}$
• $2$ で割り切れるが $4$ では割り切れない：$\{6,18\}$
• 奇数：$\{3,9,15,21\}$

同じ組の中では上の条件がすべて一致するので同値である。

よって類は高々 $1+1+4=6$ 個。

6 類が互いに区別できること
- $z=000$（$k=3,v=0$）：受理 $⟺8r\equiv 0(\mathrm{mod}3)⟺r\equiv 0(\mathrm{mod}3)$。これで $r\equiv 0$ の 4 類と残り 2 類が区別される。
- $z=10000$（$k=5,v=16$）：$v\equiv 0(\mathrm{mod}8)$ で、$32r+16\equiv 2r+1\equiv 0(\mathrm{mod}3)⟺r\equiv 1(\mathrm{mod}3)$。これで $r\equiv 1$ と $r\equiv 2$ の類が区別される。
- $z=\epsilon$：$\{0\}$ だけが受理され、$\{0\}$ と $\{12\},\{6,18\},\{3,9,15,21\}$ が区別される。
- $z=0$：受理 $⟺r\equiv 0(\mathrm{mod}12)$ なので、$\{12\}$（受理）と $\{6,18\},\{3,9,15,21\}$（非受理）が区別される。
- $z=00$：受理 $⟺r\equiv 0(\mathrm{mod}6)$ なので、$\{6,18\}$（受理）と $\{3,9,15,21\}$（非受理）が区別される。

したがって同値類はちょうど 6 個で、すべて到達可能である。マイヒル・ネローデの定理より、$L$ を受理する最小の完全 DFA の状態数は $6$ である。

$24=8\cdot 3$。DFA の状態を $\mathrm{val}(w)\mathrm{mod}24$ の剰余 $r$ とすると、初期状態は $r=0$、遷移は $r\to 2r+c(\mathrm{mod}24)$、受理状態は $r=0$ であり、これで $L$ を受理する。剰余 $r$ のうち CRT により全 24 通りが到達可能。ミーリー・ネローデ同値（ここでは「ある文字列 $x$ を続けて読んだとき、受理されるかどうか」が同じ状態同士を同一視する）で同値類を数える。

$r$ から長さ $k$ の文字列 $x$ を読むと値は $2^{k}r+\mathrm{val}(x)$（$0\le \mathrm{val}(x)<2^k$）。

(1) $r\not\equiv 0(\mathrm{mod}3)$ の場合。$k=0$ では受理されない。$k=1$ では $2r+c\equiv 0(\mathrm{mod}24)$ に $c=0$ かつ $r\equiv 0(\mathrm{mod}12)$ が必要で矛盾。$k=2$ では $4r+v\equiv 0(\mathrm{mod}24)$ ($0\le v\le 3$) に $v=0$ かつ $r\equiv 0(\mathrm{mod}6)$ が必要で矛盾。よって受理されるのは $k\ge 3$ のときだけで、このとき $2^{k}r\mathrm{mod}24$ は $r\mathrm{mod}3$ だけで決まる（$8\mid 2^k$ なので $\mathrm{mod}8$ の情報は消える）。ゆえに $r\mathrm{mod}3$ が同じなら同値で、$r\equiv 1$ と $r\equiv 2(\mathrm{mod}3)$ の 2 類。これらは十分長い文字列（$k\ge 5$ で $\mathrm{val}(x)\equiv -2^{k}r(\mathrm{mod}24)$ となるもの）で区別できる。

(2) $r\equiv 0(\mathrm{mod}3)$（$r=0,3,\dots ,21$）の場合。代表として $r=0,12,6,3$ をとる。
- $r=0$：$\epsilon$ で受理（唯一の受理状態）。
- $r=12$：$x=0$ で $24$ となり受理、$\epsilon$ は不受理。
- $r=6$（$18$ と同値）：$x=0$ では $12$ で不受理、$x=00$ で $24$ となり受理。
- $r=3$（奇数の $9,15,21$ と同値）：$x=0$ は $6$、$x=00$ は $12$、$x=000$ で $24$ となり受理。
$r=0,12,6,3$ は $\epsilon$, $0$, $00$, $000$ の受理パターンで互いに区別でき、また (1) の 2 類とも（例：$x=000$ で $r=3$ は受理、$r\equiv 1$ の類は $8$ で不受理）区別できる。$18\sim 6$、$9,15,21\sim 3$ も確認でき、これで $m=0$ の側は 4 類。

合計 $4+1+1=6$ 状態。検算：状態名を $A$（$r=0$）、$B$（$r=12$ 類）、$C$（$r\equiv 6$ 類）、$D$（$r$ 奇数かつ $3\mid r$ の類）、$E$（$r\equiv 1(\mathrm{mod}3)$ の類）、$F$（$r\equiv 2(\mathrm{mod}3)$ の類）と置いて遷移を作ると、各状態で $0,1$ の遷移がすべて 6 状態に閉じ、いずれも上の区別が保たれる。最小 DFA の状態数は 6。