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

アルファベット $\Sigma =\{a,b\}$ 上の言語 $L$ を次のように定める。$|w|$ は文字列 $w$ の長さを表す。
$$L=\{w\in {\Sigma }^{\ast }\mid |w|\text{を}3\text{で割った余りが}1\text{であり、かつ}w\text{は}ba\text{で終わる}\}$$
$L$ を受理する DFA を、次の手順で作る。

• $A_1$：それまでに読んだ文字列 $w$ について、$|w|$ を $3$ で割った余り（$0,1,2$）を状態として記憶する DFA。
• $A_2$：それまでに読んだ文字列 $w$ の末尾が $ba$ の先頭部分とどこまで一致しているか、を状態として記憶する DFA。状態は、$w$ の末尾と一致する $ba$ の先頭部分のうち最も長いものが「空文字列」「$b$」「$ba$」の $3$ 通りに対応する。
• $A$：$A_1$ と $A_2$ の積構成で作った DFA。状態は $A_1$ の状態と $A_2$ の状態の組で、$A_1$ のすべての状態と $A_2$ のすべての状態の組をすべて状態とする。各文字を読むと、組の両方の成分をそれぞれの DFA の遷移に従って同時に動かす。初期状態は両方の初期状態の組、受理状態は両方の成分が受理状態である組とする。

このとき、DFA $A$ の状態の個数を求めよ。

アルファベット $\Sigma =\{a,b\}$ 上の文字列 $w$ について、$w$ に含まれる $b$ の個数を $|w{|}_b$ と書く。言語 $L\subseteq {\Sigma }^{\ast }$ を次のように定める。
$$L=\{w\in {\Sigma }^{\ast }\mid |w{|}_b\equiv 2(\mathrm{mod}4)\text{かつ}w\text{は}ab\text{で終わる}\}$$

条件「$|w{|}_b\equiv 2(\mathrm{mod}4)$」を判定する DFA $A_1$ と、条件「$w$ は $ab$ で終わる」を判定する DFA $A_2$ を、それぞれ状態数が最小になるように作る。次に、$A_1$ の状態と $A_2$ の状態の組 $(p,s)$ をすべて状態とする積構成によって、$L$ を受理する DFA $A$ を作る。

$A$ の状態数を求めよ。

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

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