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

方針. 9 状態の DFA を作って上界を示す。次に、マイヒル・ネローデの定理（同値関係 ${\equiv }_L$ の同値類の個数が最小 DFA の状態数に等しい）を用い、互いに区別できる 9 個の文字列を挙げて下界を示す。

上界（9 状態の DFA）. 「$ab$ を含むか」を判定する DFA は次の 3 状態でできる。
- $0$: まだ $ab$ が現れておらず、最後の文字が $a$ でない（空列を含む）
- $1$: まだ $ab$ が現れておらず、最後の文字が $a$
- $2$: すでに $ab$ が現れた

遷移は $0\stackrel{a}{\to }1,0\stackrel{b}{\to }0,1\stackrel{a}{\to }1,1\stackrel{b}{\to }2,2\stackrel{a,b}{\to }2$ である。これと、長さを $3$ で割った余り $r\in \{0,1,2\}$ を数える 3 状態の DFA との直積をとると、状態 $(s,r)$（$s\in \{0,1,2\}$）からなる $9$ 状態の DFA が得られる。初期状態は $(0,0)$、受理状態は $(2,0)$ のみである。よって最小 DFA の状態数は $9$ 以下である。

下界（区別できる 9 個の文字列）. $ab$ を含まない文字列は、ちょうど $b^i{a}^j$（$i,j\ge 0$）の形の文字列である。このうち最後の文字が $a$ でないもの（$s=0$）は $j=0$、すなわち $b^i$ の形であり、最後の文字が $a$ であるもの（$s=1$）は $j\ge 1$ のものである。次の 9 個の文字列を考える。
$$\epsilon ,b,bb(s=0),aaa,a,aa(s=1),aba,abaa,ab(s=2)$$
各組の長さを $3$ で割った余りは順に $0,1,2$ である。したがって $(s,r)$ の 9 通りの組それぞれにちょうど 1 個ずつの文字列が対応している。この中の異なる 2 つ $x,y$ について、$xz\in L$ と $yz\in L$ の一方だけが成り立つ文字列 $z$ があることを示す。

$(1)$ 長さの余りが異なる場合. $z=ab{a}^k$ とし、$|x|+2+k$ が $3$ の倍数になるように $k\in \{0,1,2\}$ を選ぶ。$xz,yz$ はどちらも $ab$ を含む。$xz$ の長さは $3$ の倍数である。一方 $|y|\not\equiv |x|(\mathrm{mod}3)$ なので、$yz$ の長さは $3$ の倍数でない。よって $xz\in L,yz\notin L$ である。

$(2)$ 余りが同じで、一方が $s=2$、他方が $s\in \{0,1\}$ の場合. $s=2$ の方を $x$、他方を $y=b^i{a}^j$（$i,j\ge 0$）とし、$z=a^k$ とする。$k\in \{0,1,2\}$ は $|x|+k$ が $3$ の倍数になるように選ぶ。$xz$ は $ab$ を含み、長さは $3$ の倍数なので $xz\in L$ である。一方 $yz=b^i{a}^{j+k}$ は $ab$ を含まないので $yz\notin L$ である。

$(3)$ 余りが同じで、一方が $s=0$、他方が $s=1$ の場合. $s=0$ の方を $x=b^i$（$i\ge 0$）、$s=1$ の方を $y=b^{i^{\prime }}{a}^j$（$i^{\prime }\ge 0$, $j\ge 1$）とおく。$i$ と $i^{\prime }$ は一般に異なる（たとえば $x=b,y=a$ では $i=1,i^{\prime }=0,j=1$、$x=bb,y=aa$ では $i=2,i^{\prime }=0,j=2$）が、$|x|\equiv |y|(\mathrm{mod}3)$ である。$z=b{a}^k$ とし、$k\in \{0,1,2\}$ は $|x|+1+k$ が $3$ の倍数になるように選ぶ。
- $xz=b^{i+1}{a}^k$ は $ab$ を含まないので $xz\notin L$ である。
- $yz=b^{i^{\prime }}{a}^{j}b{a}^k$ は $j\ge 1$ より $a$ のすぐ後に $b$ が続く箇所をもつので $ab$ を含む。長さは $|y|+1+k\equiv |x|+1+k\equiv 0(\mathrm{mod}3)$ なので $yz\in L$ である。

9 個の文字列のうち異なる 2 つは、余りが異なるか、余りが同じで $s$ が異なるかのどちらかであり、$(1)$〜$(3)$ ですべての場合を尽くしている。以上より、9 個の文字列はどの 2 つも ${\equiv }_L$ で同値でない。したがって ${\equiv }_L$ の同値類は $9$ 個以上あり、最小 DFA の状態数は $9$ 以上である。

上界と合わせて、最小 DFA の状態数は $9$ である。

「$ab$ を含むか」と「長さ mod 3」の直積を考える。

$ab$ を含まない文字列の状態は 2 つに分けられる。$q_0$ は直前の文字が $a$ でない状態（空列を含む）、$q_1$ は直前の文字が $a$ で、まだ $ab$ が現れていない状態である。$ab$ を含んだ状態を $F$ とし、これは吸収状態である。

長さ mod 3 を $i\in \{0,1,2\}$ として、状態 $(q,i)$ を $q\in \{q_0,q_1,F\}$ で作ると全部で 9 状態になる。

遷移は次のとおり。
- $(q_0,i)\stackrel{a}{\to }(q_1,i+1)$
- $(q_0,i)\stackrel{b}{\to }(q_0,i+1)$
- $(q_1,i)\stackrel{a}{\to }(q_1,i+1)$
- $(q_1,i)\stackrel{b}{\to }(F,i+1)$
- $(F,i)\stackrel{a,b}{\to }(F,i+1)$

初期状態は $(q_0,0)$、受理状態は $(F,0)$ のみである。

到達可能性は次のとおり。
- $(q_0,i)$ は $b^i$ で到達できる。
- $(q_1,i)$ は $i=1,2$ では $a^i$、$i=0$ では $a^3$ で到達できる。
- $(F,i)$ は $ab$ に適当な長さの文字を足して到達できる。

よって 9 状態すべてが到達可能である。

区別可能性は次のとおり。
- $(F,i)$ どうしは、長さ mod 3 が異なるため区別できる。
- $(F,j)$ と $(q,i)$ は、$a^k$（$k\equiv -j(\mathrm{mod}3)$）で区別できる。$(F,j)$ ではこれが受理され、$(q,i)$ では $ab$ が現れないので受理されない。
- $(q,i)$ と $(q^{\prime },j)$ で $i\ne j$ の場合は、$ab$ に適当な長さの文字を足した接尾辞で区別できる。一方では受理され、他方では受理されない。
- $(q_0,i)$ と $(q_1,i)$ は、接尾辞 $b{a}^k$（長さが合うように $k$ を選ぶ）で区別できる。$q_1$ からは $b$ で $F$ に入り受理されるが、$q_0$ からは $ab$ が現れず受理されない。

したがって 9 状態はすべて互いに区別可能で、これ以上縮約できない。最小の状態数は 9 である。なお死状態は存在しない。