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

「状態数 $6$ の DFA で $L$ を受理するものが存在すること」と「$L$ を受理する DFA の状態数は必ず $6$ 以上であること」の 2 つを示す。以下、0 以上の整数 $m$ と正の整数 $k$ に対し、$m$ を $k$ で割った余りを $m\mathrm{mod}k$ と書く。

(1) 状態数 6 の DFA の構成　状態集合を $Q=\{(i,j)\mid i\in \{0,1\},j\in \{0,1,2\}\}$（6 個）とし、
$$\delta ((i,j),a)=((i+1)\mathrm{mod}2,j),\delta ((i,j),b)=(i,(j+1)\mathrm{mod}3),$$
初期状態 $(0,0)$、受理状態の集合 $F=\{(0,0)\}$ とする DFA $M$ を考える。

すべての $w\in {\Sigma }^{\ast }$ について ${\delta }^{\ast }((0,0),w)=(|w{|}_a\mathrm{mod}2,|w{|}_b\mathrm{mod}3)$ $(\ast )$ であることを、$|w|$ についての帰納法で示す。$w=\epsilon$ なら両辺とも $(0,0)$ である。$w=u\sigma$ で $u$ について $(\ast )$ が成り立つとすると、$\sigma =a$ のとき ${\delta }^{\ast }((0,0),ua)=\delta ((|u{|}_a\mathrm{mod}2,|u{|}_b\mathrm{mod}3),a)=((|u{|}_a+1)\mathrm{mod}2,|u{|}_b\mathrm{mod}3)$ であり、$|ua{|}_a=|u{|}_a+1$, $|ua{|}_b=|u{|}_b$ なのでこれは $(|ua{|}_a\mathrm{mod}2,|ua{|}_b\mathrm{mod}3)$ に等しい。$\sigma =b$ のときも、$b$ は第 2 成分だけを $1$ 進め、$|ub{|}_b=|u{|}_b+1$, $|ub{|}_a=|u{|}_a$ なので同じ理由で成り立つ。

$(\ast )$ より、$w$ が受理される $⟺$ $(|w{|}_a\mathrm{mod}2,|w{|}_b\mathrm{mod}3)=(0,0)$ $⟺$ $w\in L$。よって $M$ は $L$ を受理し、状態数は $6$ である。

(2) 状態数は 6 以上であること　$i\in \{0,1\}$, $j\in \{0,1,2\}$ に対し $x_{i,j}=a^i{b}^j$ とおく（6 個の文字列）。

*補題*　$(i,j)\ne (i^{\prime },j^{\prime })$ ならば、ある $z\in {\Sigma }^{\ast }$ が存在して、$x_{i,j}z\in L$ かつ $x_{i^{\prime },j^{\prime }}z\notin L$ となる。

*証明*　$z=a^i{b}^{(3-j)\mathrm{mod}3}$ とおく。$x_{i,j}z$ の $a$ の個数は $2i$ で偶数、$b$ の個数は $j+(3-j)\mathrm{mod}3$ で、$j=0$ なら $0$、$j=1,2$ なら $3$ なので 3 の倍数である。よって $x_{i,j}z\in L$。一方 $x_{i^{\prime },j^{\prime }}z$ の $a$ の個数は $i^{\prime }+i$、$b$ の個数は $j^{\prime }+(3-j)\mathrm{mod}3\equiv j^{\prime }-j(\mathrm{mod}3)$ である。
- $i\ne i^{\prime }$ のとき：$\{i,i^{\prime }\}=\{0,1\}$ なので $i+i^{\prime }=1$ は奇数であり、$x_{i^{\prime },j^{\prime }}z\notin L$。
- $i=i^{\prime }$ のとき：$(i,j)\ne (i^{\prime },j^{\prime })$ より $j\ne j^{\prime }$ で、$j,j^{\prime }\in \{0,1,2\}$ だから $0<|j^{\prime }-j|\le 2$、よって $j^{\prime }-j\not\equiv 0(\mathrm{mod}3)$ であり、$x_{i^{\prime },j^{\prime }}z\notin L$。

どちらの場合も主張が成り立つ。（補題の証明終わり）

背理法で示す。$L$ を受理する DFA $A=(Q^{\prime },\Sigma ,{\delta }^{\prime },p_0,F^{\prime })$ で $|Q^{\prime }|\le 5$ のものがあると仮定する。6 個の文字列 $x_{i,j}$ に状態 ${\delta }^{\prime \ast }(p_0,x_{i,j})\in Q^{\prime }$ を対応させると、鳩の巣原理より、ある $(i,j)\ne (i^{\prime },j^{\prime })$ について ${\delta }^{\prime \ast }(p_0,x_{i,j})={\delta }^{\prime \ast }(p_0,x_{i^{\prime },j^{\prime }})=p$ となる。補題の $z$ をとる。一般に ${\delta }^{\prime \ast }(q,uv)={\delta }^{\prime \ast }({\delta }^{\prime \ast }(q,u),v)$ が成り立つ（$v$ の長さについての帰納法：$v=\epsilon$ なら定義そのもの、$v=v^{\prime }\sigma$ なら両辺とも $v^{\prime }$ の場合に ${\delta }^{\prime }(\cdot ,\sigma )$ を施したものになる）ので、
$${\delta }^{\prime \ast }(p_0,x_{i,j}z)={\delta }^{\prime \ast }(p,z)={\delta }^{\prime \ast }(p_0,x_{i^{\prime },j^{\prime }}z)$$
である。よって $x_{i,j}z$ と $x_{i^{\prime },j^{\prime }}z$ は両方受理されるか両方受理されないかのどちらかであるが、これは $x_{i,j}z\in L$, $x_{i^{\prime },j^{\prime }}z\notin L$ に矛盾する。したがって $L$ を受理する DFA の状態数は $6$ 以上である。

(1), (2) より、$L$ を受理する DFA の状態数の最小値は $6$ である。$■$