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

アルファベット $\Sigma =\{a,b\}$ 上の非決定性有限オートマトン（$\epsilon$ 遷移なし）$N$ を考える。状態の集合は $\{q_0,q_1,q_2\}$、初期状態は $q_0$、受理状態は $q_2$ のみである。遷移関数 $\delta$ は次の表で与えられる（$\varnothing$ は遷移先がないことを表す）。

$N$ に部分集合構成を適用して決定性有限オートマトン $D$ をつくる。$D$ の初期状態は $\{q_0\}$ であり、$D$ の状態 $S$（$N$ の状態の部分集合）と文字 $c\in \Sigma$ に対して、遷移先を $\bigcup _{q\in S}\delta (q,c)$ と定める。$D$ の状態のうち、初期状態 $\{q_0\}$ からある入力文字列（空文字列を含む）を読んで到達できるもの（到達可能な状態）の個数を求めよ。なお、空集合 $\varnothing$ も到達できる場合は 1 つの状態として数える。

アルファベット $\Sigma =\{a,b\}$ 上の非決定性有限オートマトン（$\epsilon$ 遷移なし）$N$ を考える。状態の集合は $\{1,2,3\}$、初期状態は $1$、受理状態は $3$ のみであり、遷移関数 $\delta$ は次の表で与えられる（$\varnothing$ は遷移先がないことを表す）。

$N$ に部分集合構成を適用して、初期状態 $\{1\}$ から到達可能な状態だけからなる決定性有限オートマトン $D$ を作る。$D$ の状態（$N$ の状態の部分集合）の個数を求めよ。ただし、空集合 $\varnothing$ が初期状態から到達可能であれば、それも $1$ 個の状態として数える。

アルファベット $\Sigma =\{a,b\}$ 上の非決定性有限オートマトン（$\epsilon$ 遷移なし）$N$ を考える。状態の集合は $\{p,q,r,s\}$、初期状態は $p$、受理状態は $s$ のみであり、遷移関数 $\delta$ は次の表で与えられる（$\varnothing$ は遷移先がないことを表す）。

$N$ に部分集合構成（サブセット構成）を適用して決定性有限オートマトン $D$ を作る。ただし $D$ の状態としては、初期状態 $\{p\}$ から到達可能な部分集合だけを残す（空集合 $\varnothing$ も到達可能なら 1 つの状態として数える）。$D$ の状態数を求めよ。

アルファベット $\Sigma =\{0,1\}$ 上の決定性有限オートマトン $M$ を考える。状態の集合は $\{q_0,q_1,q_2\}$、初期状態は $q_0$、受理状態は $q_1$ と $q_2$ の 2 つであり、遷移関数 $\delta$ は次の表で与えられる。

$M$ が受理する長さ $6$ の文字列（$\Sigma$ 上の文字列）の個数を求めよ。

アルファベット $\Sigma =\{0,1\}$ 上の決定性有限オートマトン $M$ を考える。状態の集合は $\{A,B,C\}$、初期状態は $A$、受理状態は $C$ のみであり、遷移関数 $\delta$ は次の表で与えられる。

長さ $8$ の文字列 $w\in {\Sigma }^8$（全部で $2^8=256$ 個）のうち、$M$ に受理されるものの個数を求めよ。