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

マイヒル・ネローデの定理より、最小 DFA の状態数は、同値関係
$$u\equiv u^{\prime }⟺\text{すべての }v\in {\Sigma }^{\ast }\text{ について }(uv\in L_k\iff u^{\prime }v\in L_k)$$
の同値類の個数に等しい。以下、$\bar{c}$ で文字 $c$ と異なる方の文字を表す。

1. 同値類の候補を数える。

(ア) 長さ $k$ 以上の文字列 $u$：$|uv|\ge k$ なので、$uv\in L_k$ かどうかは $uv$ の末尾 $k$ 文字だけで決まる。その末尾 $k$ 文字は「$u$ の末尾 $k$ 文字」と $v$ で決まるから、末尾 $k$ 文字が同じ文字列どうしは同値である。末尾 $k$ 文字 $x_1{x}_2\cdots x_k$ は $2^k$ 通りある。

(イ) 長さ $k-1$ の文字列 $s=s_1\cdots s_{k-1}$：$t=\overline{s_{k-1}}{s}_1\cdots s_{k-1}$（長さ $k$）と同値である。実際、$v=\epsilon$ のとき $s$ は長さ不足で、$t$ は先頭 $\overline{s_{k-1}}$ と末尾 $s_{k-1}$ が異なるので、どちらも $L_k$ に属さない。$|v|\ge 1$ のとき $|sv|\ge k$ で、$sv$ と $tv$ の末尾 $k$ 文字は一致するので判定は同じである。よって長さ $k-1$ の文字列は (ア) のどれかの類に入り、新しい類を作らない。

(ウ) 長さ $m\le k-2$ の文字列：${\sum }_{m=0}^{k-2}{2}^m=2^{k-1}-1$ 個ある。

したがって同値類は高々 $2^k+2^{k-1}-1$ 個である。

2. これらがすべて互いに区別できることを示す。

まず、末尾 $k$ 文字が $x_1\cdots x_k$ の文字列に長さ $j$（$1\le j\le k-1$）の $v=v_1\cdots v_j$ をつなぐと、末尾 $k$ 文字は $x_{j+1}\cdots x_k{v}_1\cdots v_j$ になる。よって受理される条件は $x_{j+1}=v_j$ である。

(i) (ア) の異なる 2 つの類（末尾 $x$ と $y$）：ある $i\ge 2$ で $x_i\ne y_i$ ならば、$j=i-1$、$v=a^{j-1}{x}_i$ とすると、前者は受理され、後者は受理されない。$x_2\cdots x_k=y_2\cdots y_k$ ならば $x_1\ne y_1$ かつ $x_k=y_k$ である。このとき $v=\epsilon$ とすると、一方だけが受理される。

(ii) (ア) の類と、長さ $m\le k-2$ の文字列 $s$：$v=x_2$（1 文字）とすると、前者は受理される。$sv$ は長さ $m+1\le k-1$ なので受理されない。

(iii) 長さ $m<m^{\prime }\le k-2$ の $s,s^{\prime }$：$j=k-m^{\prime }$、$v=a^{j-1}{s}_1^{\prime }$ とすると、$s^{\prime }v$ は長さ $k$ で先頭と末尾がともに $s_1^{\prime }$ なので受理される。$sv$ は長さ $m+j<k$ なので受理されない。

(iv) 同じ長さ $m\le k-2$ で、$i$ 文字目が異なる $s,s^{\prime }$：$j=k-m+i-1$ とする（$2\le j\le k-1$）。このとき $|sv|=k+i-1$ で、末尾から $k$ 番目は $sv$ の $i$ 文字目 $s_i$ である。$v=a^{j-1}{s}_i$ とすると $sv$ は受理され、$s^{\prime }v$ は末尾から $k$ 番目が $s_i^{\prime }\ne s_i$ なので受理されない。

以上より同値類はちょうど
$$2^k+2^{k-1}-1=3\cdot 2^{k-1}-1$$
個であり、これが最小 DFA の状態数である。

（確認：$k=2$ のとき $L_2$ は $aa$ または $bb$ で終わる文字列全体で、状態数は $5$。$k=3$ のときは $11$ である。）

$L_k$ のミニマル DFA の状態数を、マイヒル・ネローデ同値類の個数として数える。

長さ $k$ 以上の語。 末尾 $k$ 文字を $d_1{d}_2\cdots d_k$ とする。続く文字列 $z$ について次が成り立つ。
- $|z|=m$（$1\le m\le k-1$）のとき、$wz\in L_k$ は $d_{m+1}$ と $z$ の最後の文字が等しいことと同値である。
- $m\ge k$ のとき、結果は $z$ だけで決まる。
- $z=\epsilon$ のとき、結果は $d_1=d_k$ かどうかで決まる。

よって $w$ の将来の振る舞いは、$(d_2,\dots ,d_k)$ と、$w\in L_k$ か否かの 1 ビットで決まる。これらは互いに区別できる。
- $d_{m+1}$ が異なれば、長さ $m$ の適当な $z$ で区別できる。
- 1 ビットが異なれば、$z=\epsilon$ で区別できる。

どの組合せも長さ $k$ の語で実現できるので、この型の状態は $2^{k-1}\cdot 2=2^k$ 個ある。

長さ $k-1$ 以下の語。
- 長さ $k-1$ の語 $e_1\cdots e_{k-1}$ は、$d_2\cdots d_k=e_1\cdots e_{k-1}$ で受理されない長い語と同値である。すでに数えた状態に含まれる。
- 長さ $j\le k-2$ の語は、長さ 1 の $z$ でも受理されない（$m=1<k-j$）。長い語は、$z$ の最後の文字を $d_{m+1}$ に合わせれば長さ $m$ の受理される $z$ が必ず存在するので、区別できる。
- 長さ $j\le k-2$ の語どうしも、長さが異なれば $m=k-j^{\prime }$（$j<j^{\prime }$）で区別できる。長さが同じで内容が異なる場合も区別できる。

この型の状態は ${\sum }_{j=0}^{k-2}{2}^j=2^{k-1}-1$ 個ある。

合計。 $2^k+2^{k-1}-1=3\cdot 2^{k-1}-1$ 個。

検算。 $k=2$ では $5$ 個になる。$\epsilon$ と、(最後の文字 $a$ または $b$) × (受理か否か) の 4 状態である。これは「$aa$ または $bb$ で終わる語」の最小 DFA と一致する。

答え: $3\cdot 2^{k-1}-1$