言語の条件から DFA を作る（余り・接尾辞・積構成）

アルファベット $\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 =\{0,1,2\}$ 上の文字列 $w=c_1{c}_2\cdots c_n$（$n\ge 0$）を 3 進数として読んだ値を $\mathrm{val}(w)$ と書く（先頭に $0$ があってもよい。空文字列 $\epsilon$ については $\mathrm{val}(\epsilon )=0$ とする）。たとえば $\mathrm{val}(021)=0\cdot 9+2\cdot 3+1=7$ である。

言語
$$L=\{w\in {\Sigma }^{\ast }\mid \mathrm{val}(w)\text{ は }4\text{ の倍数}\}$$
を受理する DFA を、次のように作る。

• 状態の集合は $Q=\{0,1,2,3\}$ とし、状態 $r$ は「ここまで読んだ文字列 $w$ について $\mathrm{val}(w)$ を $4$ で割った余りが $r$ である」ことを表す。
• 初期状態は $0$、受理状態は $0$ のみとする。
• 遷移関数 $\delta (r,c)$ は、余りが $r$ の文字列の後ろに文字 $c$ を 1 つ付け加えたときの、新しい値を $4$ で割った余りとする。

この DFA の遷移表（4 つの状態 × 3 つの文字で、全部で $12$ 個の欄がある）を完成させたとき、遷移先が受理状態 $0$ である欄の個数を求めよ。

アルファベット $\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$ を次のように定める。
$$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）とする。