マイヒル・ネローデの定理と最小状態数

アルファベット $\Sigma =\{a,b\}$ 上の言語 $L$ を次のように定める。
$$L=\{w\in {\Sigma }^{\ast }\mid |w|\ge 2\text{ かつ }w\text{ の後ろから }2\text{ 番目の文字が }a\}$$
たとえば $ab,aab,baa,abab$ は $L$ に属する。一方、$\epsilon ,a,ba,aba$ は $L$ に属さない。

$L$ を受理する最小の完全 DFA（すべての状態と文字について遷移が定義された決定性有限オートマトン）の状態数を求めよ。

アルファベット $\Sigma =\{a,b\}$ 上の言語 $L\subseteq {\Sigma }^{\ast }$ を次のように定めます。
$$L=\{w\in {\Sigma }^{\ast }\mid |w|\ge 2\text{ かつ }w\text{ の後ろから 2 文字目が }a\}$$
たとえば $aa,ab,bab\in L$ であり、$\epsilon ,a,ba,abb\notin L$ です。

$L$ を受理する完全な決定性有限オートマトン（DFA）のうち、状態数が最小のものの状態数を求めてください。ここで完全な DFA とは、すべての状態とすべての文字に対して遷移が定義されている DFA のことです。

アルファベット $\Sigma =\{a,b\}$ 上の言語 $L\subseteq {\Sigma }^{\ast }$ を
$$L=\{w\in {\Sigma }^{\ast }\mid w\text{ は }abb\text{ で終わる}\}$$
と定める。マイヒル・ネローデの定理を用いて、$L$ を受理する最小の完全 DFA（すべての状態とすべての文字について遷移が定義されている決定性有限オートマトン）の状態数を求めよ。

アルファベット $\Sigma =\{a,b\}$ 上の言語 $L$ を次のように定める。
$$L=\{w\in {\Sigma }^{\ast }\mid w\text{ は部分文字列として }ab\text{ を含み、かつ }|w|\text{ は }3\text{ の倍数}\}$$
ここで $|w|$ は $w$ の長さを表し、部分文字列とは連続した文字の並びのことである（長さ $0$ の空列 $\epsilon$ の長さは $0$ で、$0$ は $3$ の倍数とする）。

$L$ を受理する決定性有限オートマトン（DFA）のうち、状態数が最小のものの状態数を求めよ。ただし、DFA の遷移関数はすべての状態とすべての入力記号について定義されている（全域的である）ものとする。

アルファベット $\Sigma =\{a,b\}$ 上の文字列 $w$ について、$w$ に含まれる $a$ の個数を $|w{|}_a$ と書く。言語 $L\subseteq {\Sigma }^{\ast }$ を
$$L=\{w\in {\Sigma }^{\ast }\mid |w{|}_a\text{は}3\text{の倍数であり、かつ}w\text{は}ab\text{で終わる}\}$$
と定める（たとえば $aaab\in L$、$abaab\in L$、$ab\notin L$、$aaabb\notin L$）。$L$ を受理する決定性有限オートマトン（DFA）のうち状態数が最小のものの状態数を求めよ。ただし、DFA の遷移関数はすべての状態とすべての入力記号に対して定義されている（全域的である）ものとし、状態数には到達可能な状態だけを数える。

アルファベット $\Sigma =\{a,b\}$ 上の文字列 $w$ に含まれる $a$ の個数を $|w{|}_a$、$b$ の個数を $|w{|}_b$ と書き、言語
$$L=\{w\in {\Sigma }^{\ast }\mid |w{|}_a\equiv 0(\mathrm{mod}2)\text{かつ}|w{|}_b\equiv 0(\mathrm{mod}3)\}$$
を考える。ここで決定性有限オートマトン（DFA）とは、有限の状態集合 $Q$、遷移関数 $\delta :Q\times \Sigma \to Q$（すべての状態と文字に対して遷移先がただ 1 つ定まる）、初期状態 $q_0\in Q$、受理状態の集合 $F\subseteq Q$ の組 $(Q,\Sigma ,\delta ,q_0,F)$ とし、拡張遷移関数を ${\delta }^{\ast }(q,\epsilon )=q$、${\delta }^{\ast }(q,u\sigma )=\delta ({\delta }^{\ast }(q,u),\sigma )$ で定め、$w$ が受理されるのは ${\delta }^{\ast }(q_0,w)\in F$ のときとする。DFA の状態数とは $|Q|$ のことである。

$L$ を受理する DFA の状態数の最小値が $6$ であることを証明せよ。

アルファベット $\Sigma =\{0,1\}$ 上の言語 $L$ を次のように定める。

文字列 $w=c_1{c}_2\cdots c_n\in {\Sigma }^{\ast }$（$n\ge 0$）を 2 進数として読んだ値を $\mathrm{val}(w)={\sum }_{i=1}^n{c}_i{2}^{n-i}$ とする（先頭に $0$ が続いてもよく、空文字列 $\epsilon$ の値は $0$ とする）。このとき
$$L=\{w\in {\Sigma }^{\ast }\mid \mathrm{val}(w)\text{は}24\text{の倍数}\}$$
とする。$L$ を受理する完全な決定性有限オートマトン（DFA。すべての状態とすべての入力記号に対して遷移が定義されているもの）のうち、状態数が最小のものの状態数を求めよ。

アルファベット $\Sigma =\{a,b\}$ 上の文字列 $w$ について、$w$ に含まれる $a$ の個数を $|w{|}_a$ と書く。言語 $L\subseteq {\Sigma }^{\ast }$ を
$$L=\{w\in {\Sigma }^{\ast }\mid |w{|}_a\text{ は }3\text{ の倍数であり、かつ }w\text{ は }ab\text{ で終わる}\}$$
と定める（$|w{|}_a=0$ も $3$ の倍数とみなす）。$L$ を受理する決定性有限オートマトン（DFA）のうち、状態数が最小のものの状態数を求めよ。ただし、DFA の遷移関数はすべての状態とすべての入力記号に対して定義されている（完全な DFA）とする。

$k$ を $2$ 以上の整数とする。アルファベット $\Sigma =\{a,b\}$ 上の言語 $L_k\subseteq {\Sigma }^{\ast }$ を
$$L_k=\{w=c_1{c}_2\cdots c_n\in {\Sigma }^{\ast }\mid n\ge k\text{ かつ }{c}_{n-k+1}=c_n\}$$
と定める。つまり $L_k$ は、長さが $k$ 以上で、末尾から $k$ 番目の文字と最後の文字が等しい文字列全体の集合である。$L_k$ を受理する最小の決定性有限オートマトン（遷移関数はすべての状態とすべての文字について定義されているものとする）の状態数を $k$ の式で求めよ。