オートマトン・形式言語

終端記号 $\{a,b,c\}$、非終端記号 $\{S\}$、開始記号 $S$ をもち、次の 3 つの生成規則からなる文脈自由文法 $G$ を考える。
$$S\to aSa,S\to bSb,S\to c$$
文字列 $abbcbba$ は $G$ で生成される。この文字列の $S$ からの導出に対応する導出木（構文木）を描いたとき、その頂点の個数を求めよ。ただし、頂点は根と葉を含めたすべての頂点（非終端記号のラベルをもつ頂点と終端記号のラベルをもつ頂点）を数える。

終端記号 $\{a,b,c\}$、非終端記号 $\{S,T\}$、開始記号 $S$ をもち、次の 4 つの生成規則からなる文脈自由文法 $G$ を考える。
$$S\to aSc,S\to T,T\to bT,T\to b$$
文字列 $w=aabbbcc$ は $G$ で生成される。開始記号 $S$ から $w$ を得る最左導出を書いたとき、生成規則を何回適用するか（導出のステップ数）を求めよ。

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

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

アルファベット $\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$ を考える。状態の集合は $\{q_0,q_1,q_2\}$、初期状態は $q_0$、受理状態は $q_0$ と $q_1$ の 2 つであり、遷移関数 $\delta$ は次の表で与えられる。

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

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

$N$ に部分集合構成を適用して DFA $D$ をつくる。$D$ の初期状態は $\{A\}$ であり、$D$ の状態 $S$（$N$ の状態の部分集合）と入力 $x$ に対する遷移先は、$S$ の各状態から $x$ で移れる状態をすべて集めた集合である。$D$ の初期状態 $\{A\}$ から何文字か（0 文字も含む）読んで到達できる $D$ の状態の個数を求めよ。ただし、空集合 $\varnothing$ も到達できる場合は 1 つの状態として数える。

アルファベット $\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\}$ 上の言語 $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\}$ 上の決定性有限オートマトン（DFA）$M$ を考える。状態の集合は $\{q_0,q_1,q_2,q_3,q_4,q_5\}$、初期状態は $q_0$、受理状態は $q_2$ と $q_5$ の 2 つである。遷移関数 $\delta$ は次の表で与えられる。

$M$ が受理する言語と同じ言語を受理する DFA のうち、状態数が最小のもの（最小 DFA）の状態数を求めよ。ただし、DFA の遷移関数はすべての状態と入力文字について定義されているものとする。

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

$M$ と同じ言語を受理する DFA のうち、状態数が最小のもの（最小 DFA）の状態数を求めよ。

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

$M$ が受理する言語と同じ言語を受理する DFA のうち、状態数が最小のもの（最小 DFA）の状態数を求めよ。ただし、DFA の遷移関数はすべての状態と文字に対して定義されているものとする。

終端記号 $\{a,b,c\}$、非終端記号 $\{S,A,B,C\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AB\mid SC,B\to SB\mid b,A\to a,C\to c$$
文字列 $w=abcb$（長さ $4$）について CYK 法の表を作る。$w$ の $i$ 文字目から $j$ 文字目までの部分文字列を $w_{i..j}$ とし、$w_{i..j}$ を導出できる非終端記号全体の集合を $V_{i,j}$ とする（$1\le i\le j\le 4$）。

全体の欄 $V_{1,4}$ として正しいものを、次のア〜エから 1 つ選べ。

ア　$\varnothing$（空集合）

イ　$\{S\}$

ウ　$\{B\}$

エ　$\{S,B\}$

終端記号 $\{a,b\}$、非終端記号 $\{S,A,B,C\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AC\mid BB,A\to a,B\to AS\mid b,C\to SB\mid b$$
文字列 $w=aabb$ の $i$ 文字目から $j$ 文字目までの部分文字列を $w_{i..j}$ とし、$w_{i..j}$ を導出できる非終端記号全体の集合を $V_{i,j}$ と書く（$1\le i\le j\le 4$）。CYK 法で表を埋めて、$V_{1,4}$ を求めよ。

終端記号 $\{0,1\}$、非終端記号 $\{S,A,B,C\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AC\mid BS,C\to SB\mid 1,A\to 0,B\to 1$$
文字列 $w=0011$ の $i$ 文字目を $w_i$ とし、$1\le i\le j\le 4$ に対して、部分文字列 $w_i{w}_{i+1}\cdots w_j$ を生成する非終端記号全体の集合を $X_{i,j}$ とする。CYK 法で $X_{i,j}$ の表を短い部分文字列から順に埋めたとき、全体の欄 $X_{1,4}$ に入る集合として正しいものを、次のア〜エから 1 つ選べ。

ア　$\varnothing$　　イ　$\{S\}$　　ウ　$\{C\}$　　エ　$\{S,C\}$

両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 状態の集合は $\{q_0,q_1,h\}$ である。初期状態は $q_0$、停止状態は $h$ である。$h$ からの遷移はなく、$M$ は $h$ に入った時点で停止する。
• 入力アルファベットは $\Sigma =\{0,1\}$、テープ記号の集合は $\Gamma =\{0,1,\bigsqcup \}$ である（$\bigsqcup$ は空白記号）。
• 遷移関数 $\delta$ は次の表で与えられる。表の各欄の $(p,c,D)$ は「状態 $p$ に移り、ヘッドの位置のマスに記号 $c$ を書き、ヘッドを向き $D$ に 1 マス動かす」ことを表す（$\mathrm{R}$ は右、$\mathrm{L}$ は左）。

はじめ、テープには入力文字列 $1011$ が左から順に連続する 4 マスに書かれ、それ以外のマスはすべて空白記号 $\bigsqcup$ である。ヘッドは入力の最も左の文字（左端の $1$）のマスにあり、状態は $q_0$ である。

遷移を 1 回行うことを 1 ステップと数える（$h$ に入る遷移も 1 ステップに数える）。$M$ が停止するまでのステップ数を求めよ。

右方向に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 入力アルファベット: $\Sigma =\{1,+\}$
• テープ記号の集合: $\Gamma =\{1,+,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 状態の集合: $\{q_0,q_1,q_2,h\}$。初期状態は $q_0$、停止状態は $h$ である。$h$ からの遷移はなく、$M$ は状態 $h$ に入った時点で停止する。
• 遷移関数 $\delta$ は次の表のとおりである。$\delta (q,s)=(q^{\prime },s^{\prime },D)$ は「状態 $q$ でヘッドが記号 $s$ を読んでいるとき、そのマスに $s^{\prime }$ を書き、ヘッドを $D$ の向き（$\mathrm{R}$ は右へ 1 マス、$\mathrm{L}$ は左へ 1 マス）に動かし、状態を $q^{\prime }$ にする」という意味である。表にない組は、以下の計算では現れない。

最初、テープの左端から順に入力 $11+111$ が書かれ、それより右のマスはすべて $\bigsqcup$ である。ヘッドは左端のマス（入力の 1 文字目）にあり、状態は $q_0$ である。遷移を 1 回行うことを 1 ステップと数えるとき、$M$ が停止するまでのステップ数を求めよ。

1 テープ決定性チューリング機械 $M$ を考える。

• 入力アルファベット: $\Sigma =\{1,+\}$
• テープ記号の集合: $\Gamma =\{1,+,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 状態の集合: $\{q_0,q_1,q_2,h\}$。初期状態は $q_0$、停止状態は $h$ である（$h$ からの遷移はない）。
• テープは右に無限に続き、はじめは左端のマスから順に入力文字列が書かれ、残りのマスはすべて $\bigsqcup$ である。ヘッドは左端のマス（入力の 1 文字目）にあり、状態は $q_0$ である。

遷移関数 $\delta$ は次の表で与えられる。表の $(p,c,D)$ は「状態 $p$ に移り、いま読んでいるマスに記号 $c$ を書き、ヘッドを $D$ の向き（$R$ は右、$L$ は左）に 1 マス動かす」ことを表す。「—」の組では遷移は定義されていない。

遷移を 1 回適用することを 1 ステップと数える。入力文字列 $111+11$ を与えて $M$ を動かしたとき、状態が $h$ になるまでに何ステップかかるか求めよ。

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

$n$ を正の整数とする。$M$ に受理される長さ $n$ の文字列の個数を、遷移を数える行列の対角化を用いて $n$ の式で表せ。

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

$n$ を $0$ 以上の整数とする。$M$ が受理する長さ $n$ の文字列（$\Sigma$ の記号を $n$ 個並べたもの。$n=0$ のときは空文字列）の個数 $a_n$ を、遷移を数える行列の対角化を用いて $n$ の式で表せ。

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

$n$ を正の整数とする。$M$ が受理する長さ $n$ の文字列の個数を、遷移を数える行列の対角化を用いて $n$ の式で表せ。

アルファベット $\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\}$ 上の正規表現
$$r=(a+bb{)}^{\ast }$$
を考え、$r$ が表す言語を $L(r)$ とする（$+$ は和集合、${}^{\ast }$ はクリーネ閉包を表す）。$L(r)$ に属する長さ $10$ の文字列の個数を求めよ。

アルファベット $\Sigma =\{a,b\}$ 上の正規表現
$$r=(a+bb{)}^{\ast }$$
を考え、$r$ が表す言語を $L(r)$ とします（$+$ は和集合、${}^{\ast }$ はクリーネ閉包を表し、空列も $L(r)$ に含まれます）。長さ $10$ の文字列のうち、$L(r)$ に属するものの個数を求めなさい。

アルファベット $\Sigma =\{a,b,c\}$ 上の正規表現
$$r=(a+b+cc{)}^{\ast }$$
を考え、$r$ が表す言語を $L(r)$ とします（$+$ は和集合、${}^{\ast }$ はクリーネ閉包を表します）。$L(r)$ に属する長さ $6$ の文字列の個数を求めなさい。

終端記号 $\{a,b\}$、非終端記号 $\{S,L,R\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to LS\mid SR\mid b,L\to a,R\to a$$
文字列 $w=aaba$ の $G$ における導出木（開始記号 $S$ を根とし、葉を左から読むと $w$ になるもの）の個数を求めよ。

終端記号 $\{a,b,c\}$、非終端記号 $\{S,X,Y,A,B,C\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to XC\mid AY\mid SC,X\to AB,Y\to BC\mid YC,$$
$$A\to a,B\to b,C\to c$$
文字列 $w=abcc$ について、$S$ を根とし $w$ を生成する導出木（構文木）の個数を求めよ。

終端記号 $\{x,+\}$、非終端記号 $\{E,P,O\}$、開始記号 $E$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$E\to EP\mid x,P\to OE,O\to +$$
長さ $5$ の文字列 $w=x+x+x$（左から順に $x,+,x,+,x$ の $5$ 文字）について、根が $E$ である $w$ の導出木の個数を求めよ。

アルファベット $\Sigma =\{0,1\}$ 上の決定性有限オートマトン $M$ を考える。状態の集合は $\{q_0,q_1,q_2\}$、初期状態は $q_0$、受理状態は $q_2$ のみであり、遷移関数 $\delta$ は次の表で与えられる（行が現在の状態、列が読む文字、表の中身が次の状態）。

次の $5$ つの文字列のうち、$M$ が受理するものの番号の集合を求めよ。
$$(1)10(2)110(3)101(4)0111(5)1011$$

アルファベット $\{a,b\}$ 上の正規表現
$$r=a^{\ast }b{a}^{\ast }$$
を考える。次の文字列のうち、$r$ が表す言語 $L(r)$ に属するものをすべて選べ。

ア: $b$

イ: $aab$

ウ: $abab$

エ: $baa$

オ: $aa$

終端記号 $\{a,b\}$、非終端記号 $\{S,A,B\}$、開始記号 $S$ をもつ、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AS\mid SB\mid AB,A\to a,B\to b$$
文字列 $w=aaabbb$ の $G$ における構文木（導出木）の個数を求めよ。

終端記号 $\{a,b\}$、非終端記号 $\{S,A,B,C\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to SS\mid AB\mid AC,C\to SB,A\to a,B\to b$$
長さ $10$ の文字列
$$w=ababaabbab$$
は $G$ で生成される。$w$ の（開始記号 $S$ を根とする）導出木の個数を求めよ。

入力アルファベット $\Sigma =\{0,1\}$、テープ記号の集合 $\Gamma =\{0,1,\bigsqcup \}$（$\bigsqcup$ は空白記号）をもつ 1 テープ決定性チューリング機械 $M$ を考える。状態の集合は $\{q_0,q_1,q_h\}$ で、初期状態は $q_0$、$q_h$ は停止状態である（$q_h$ に入った時点で $M$ は停止する）。遷移関数 $\delta$ は次の表で与えられる。表の各欄の $(q^{\prime },c,D)$ は「次の状態を $q^{\prime }$ にし、ヘッドの位置の記号を $c$ に書き換え、ヘッドを $D$ の向き（$\mathrm{L}$ は左、$\mathrm{R}$ は右）に 1 マス動かす」ことを表す。

テープは両側に無限に続き、はじめは入力文字列が連続するマスに書かれ、それ以外のマスはすべて $\bigsqcup$ である。ヘッドは最初、入力文字列の最も左の記号の上にある。遷移関数を 1 回適用することを 1 ステップと数える。

入力文字列 $w=1101011$ を与えたとき、$M$ が停止するまでのステップ数を求めよ。

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

$\Sigma$ 上の長さ $10$ の文字列のうち、$M$ が受理するものの個数を求めよ。

終端記号 $\{a,b\}$、非終端記号 $\{S\}$、開始記号 $S$ をもち、次の 3 つの生成規則からなる文脈自由文法 $G$ を考える。
$$S\to SS,S\to aSb,S\to ab$$
文字列
$$w=aabababbababab$$
（長さ $14$）について、$G$ における $w$ の導出木（構文木）の個数を求めよ。

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

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

終端記号 $\{a,b\}$、非終端記号 $\{S,A\}$、開始記号 $S$ をもち、次の 4 つの生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to SA,S\to AS,S\to b,A\to a$$
文字列 $w=aabaa$ について、$G$ における $w$ の構文木（導出木）の個数を求めよ。ここで、構文木の個数は $w$ の最左導出の個数に等しい。

非終端記号 $S$（開始記号）、終端記号 $a,b$ をもつ文脈自由文法 $G$ の生成規則を
$$S\to aS,S\to Sb,S\to \epsilon$$
の 3 つとする（$\epsilon$ は空列）。ここで $S$ から終端記号列 $w$ への導出とは、文形式の列 ${\alpha }_0=S\Rightarrow {\alpha }_1\Rightarrow \cdots \Rightarrow {\alpha }_k=w$（$k$ は正の整数）であって、各 ${\alpha }_{t-1}\Rightarrow {\alpha }_t$ が ${\alpha }_{t-1}$ の中の 1 つの $S$ を 1 つの生成規則の右辺で置き換えたものであるものをいう。2 つの導出は、文形式の列として異なるとき異なるものと数える。

$m,n$ を 0 以上の整数とする。$S$ から $a^m{b}^n$ への導出の個数がちょうど $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ であることを証明せよ。

アルファベット $\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 の遷移関数はすべての状態とすべての入力記号について定義されている（全域的である）ものとする。

終端記号 $\{a,b\}$、非終端記号 $\{S,T,A,B\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AB\mid AT\mid SB,T\to SB,A\to a,B\to b$$
長さ $8$ の文字列 $w=aaabbbbb$ について、$S$ を根とし葉を左から読むと $w$ になる $G$ の構文木（導出木）は何通りあるか。すなわち、$S$ から $w$ への最左導出の個数を求めよ。

両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 状態の集合は $\{q_0,q_1,q_2,h\}$ である。初期状態は $q_0$、停止状態は $h$ である。$h$ からの遷移はなく、$h$ に入った時点で $M$ は停止する。
• 入力アルファベットは $\{0,1\}$、テープ記号の集合は $\{0,1,\bigsqcup \}$ である（$\bigsqcup$ は空白記号）。
• 遷移関数 $\delta$ は次の表で与えられる。表の各欄の $(p,c,D)$ は「状態 $p$ に移り、ヘッドの位置に記号 $c$ を書き込み、ヘッドを向き $D$ に 1 マス動かす」ことを表す。$L$ は左、$R$ は右である。

最初、テープには入力文字列 $w=10110111$ が左から順に 1 マスに 1 文字ずつ書かれている。それ以外のマスはすべて $\bigsqcup$ である。ヘッドは $w$ の左端の文字の上にあり、状態は $q_0$ である。

遷移関数を 1 回適用することを 1 ステップと数える。$h$ に移る遷移も 1 ステップに含める。$M$ が停止するまでのステップ数を求めよ。

次の 1 テープ決定性チューリング機械 $M$ を考える。

• 状態の集合: $\{q_0,q_1,q_2,q_3,q_{\mathrm{acc}},q_{\mathrm{rej}}\}$。初期状態は $q_0$、受理状態は $q_{\mathrm{acc}}$、拒否状態は $q_{\mathrm{rej}}$
• 入力アルファベット: $\{a,b\}$、テープアルファベット: $\{a,b,X,Y,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 遷移関数 $\delta$ は次の表のとおり。表の「$(p,c,D)$」は「状態を $p$ に変え、いま読んでいるマスに $c$ を書き、ヘッドを $D$ の向き（$\mathrm{R}$ は右、$\mathrm{L}$ は左）に 1 マス動かす」ことを表す。表にない（状態, 記号）の組では、$M$ は $q_{\mathrm{rej}}$ に移って停止する。

テープは右に無限に続き、はじめは入力文字列が左端のマスから書かれ、残りのマスはすべて $\bigsqcup$ である。ヘッドははじめ左端のマス（入力の 1 文字目）にあり、状態は $q_0$ である。$M$ は $q_{\mathrm{acc}}$ または $q_{\mathrm{rej}}$ に入った時点で停止する。

入力 $aaabbb$ に対して $M$ を動かしたとき、$M$ が停止するまでに適用される遷移の回数（停止状態に入る遷移も 1 回と数える）を求めよ。

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

$n$ を $0$ 以上の整数とする。$M$ が受理する長さ $n$ の文字列の個数を $n$ の式で表せ。

アルファベット $\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\}$ 上の非決定性有限オートマトン（$\epsilon$ 遷移なし）$N$ を考える。状態の集合は $\{0,1,2,3\}$、初期状態は $0$、受理状態は $2$ と $3$ の 2 つであり、遷移関数 $\delta$ は次の表で与えられる（$\varnothing$ はその記号での遷移先がないことを表す）。

$N$ が受理する言語 $L(N)$ を受理する決定性有限オートマトン（遷移関数がすべての状態と記号について定義されたもの）のうち、状態数が最小のものの状態数を求めよ。

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

0 以上の整数 $n$ に対し、$M$ が受理する長さ $n$ の文字列（長さ $0$ の文字列は空列 $\epsilon$ のみとする）の個数を $A_n$ とする。すべての 0 以上の整数 $n$ について
$$A_n=\frac{2^n+2(-1{)}^n}{3}$$
が成り立つことを証明せよ。

両側に無限に続く 1 本のテープをもつ決定性チューリング機械 $M$ を考える。テープの各セルを整数で番号付けする（セル $i$ の右隣はセル $i+1$）。入力記号の集合は $\{0,1\}$、テープ記号の集合は $\{0,1,\bigsqcup \}$（$\bigsqcup$ は空白記号）、状態の集合は $\{q_0,q_1,q_h\}$ で、初期状態は $q_0$、停止状態は $q_h$ である。遷移関数 $\delta$ は次の表で与えられる（$\delta (q,s)=(q^{\prime },s^{\prime },D)$ は、状態 $q$ でヘッドが記号 $s$ を読んだとき、そのセルに $s^{\prime }$ を書き、ヘッドを $D$ の向き（$\mathrm{L}$ は左、$\mathrm{R}$ は右）に 1 セル動かし、状態 $q^{\prime }$ に移ることを表す）。

$q_h$ からの遷移はなく、$M$ は状態 $q_h$ に入った時点で停止する。遷移関数を 1 回適用することを 1 ステップと数える。

$n$ を正の整数とし、入力 $w=w_1{w}_2\cdots w_n$（各 $w_i\in \{0,1\}$）を、セル $1,2,\dots ,n$ に $w_1,\dots ,w_n$ を書き、それ以外のセルをすべて $\bigsqcup$ とし、ヘッドをセル $1$ に置いて状態 $q_0$ から動かす。$w$ を左端を最上位の桁とする 2 進数として読んだ値を $N={\sum }_{i=1}^n{w}_i{2}^{n-i}$ とし、$w$ の末尾に連続して並ぶ $1$ の個数（$w_n=0$ なら $0$）を $t$ とする。

このとき、$M$ はちょうど $n+t+2$ ステップで停止し、停止時のテープ上の $\bigsqcup$ でない記号は連続したいくつかのセルに並んで 1 つの文字列 $x$ をなし、$x$ を左端を最上位の桁とする 2 進数として読んだ値が $N+1$ であることを証明せよ。ここで $x$ の先頭に $0$ が並んでいてもよく（たとえば $w=0010$ なら $x=0011$）、$x$ が置かれるセルの範囲は入力が置かれたセル $1,\dots ,n$ と一致するとは限らない。

アルファベット $\Sigma =\{a,b\}$ 上の正規表現を考える。正規表現 $r$ が表す言語を $L(r)$ と書き、$L(r+s)=L(r)\cup L(s)$、$L(rs)=L(r)L(s)$（連接）、$L(r^{\ast })={\bigcup }_{m\ge 0}L(r{)}^m$（$L(r{)}^0=\{\epsilon \}$、$\epsilon$ は空列）と定める。文字列 $w\in {\Sigma }^{\ast }$ に含まれる文字 $a$ の個数を $|w{|}_a$、$w$ の長さを $|w|$ と書く。

正規表現
$$R=(b+a{b}^{\ast }a{)}^{\ast }$$
について、
$$L(R)=\{w\in {\Sigma }^{\ast }\mid |w{|}_a\text{ は偶数}\}$$
が成り立つことを証明せよ。

アルファベット $\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$ であることを証明せよ。

終端記号 $\{a,b\}$、非終端記号 $\{S,T,U,A,B\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AB\mid BA\mid SS\mid AT\mid BU,T\to SB,U\to SA,A\to a,B\to b$$
文字列 $w=abaabbab$（長さ $8$）について、$G$ における $w$ の相異なる構文木（導出木）の個数を求めよ。なお、これは $S$ から $w$ への相異なる最左導出の個数に等しい。

アルファベット $\Sigma =\{a,b,c\}$ 上の決定性有限オートマトン $M$ を考えます。状態の集合は $\{p,q,r,s\}$、初期状態は $p$、受理状態は $p$ のみです。遷移関数 $\delta$ は次の表で与えられます。

$n$ を $0$ 以上の整数とします。$M$ が受理する長さ $n$ の文字列の個数を $n$ の式で求めてください。

アルファベット $\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\}$ 上の正規表現
$$r=(a+ab+abb{)}^{\ast }$$
を考え、$r$ が表す言語を $L(r)$ とする（$+$ は和集合、${}^{\ast }$ はクリーネ閉包を表す）。

長さ $8$ の文字列 $w\in {\Sigma }^{\ast }$ のうち、次の 2 つの条件をともに満たすものの個数を求めよ。

• $w\in L(r)$
• $w$ に含まれる $b$ の個数が偶数である（$0$ 個も偶数とみなす）

アルファベット $\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）とする。

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

$n$ を正の整数とする。$M$ が受理する長さ $n$ の文字列の個数を $n$ の式で表せ。

入力アルファベット $\Sigma =\{a,b\}$、テープ記号の集合 $\Gamma =\{a,b,X,Y,\bigsqcup \}$（$\bigsqcup$ は空白記号）をもつ 1 テープ決定性チューリング機械 $M$ を考える。

• 状態の集合は $\{q_0,q_1,q_2,q_3,q_{\mathrm{acc}},q_{\mathrm{rej}}\}$ であり、初期状態は $q_0$、受理状態は $q_{\mathrm{acc}}$、拒否状態は $q_{\mathrm{rej}}$ である。$M$ は $q_{\mathrm{acc}}$ または $q_{\mathrm{rej}}$ に入った時点で停止する。
• テープのマスには左から順に番号 $1,2,3,\dots$ が付いており、入力 $w$ はマス $1$ から $|w|$ に 1 文字ずつ書かれ、ほかのマスはすべて $\bigsqcup$ である。最初、ヘッドはマス $1$ にある。
• 遷移関数 $\delta$ は次の表で与えられる。表の $(p,c,D)$ は「状態 $p$ に移り、いまのマスに記号 $c$ を書き、ヘッドを $D$ の向きに 1 マス動かす（$R$ は右、$L$ は左）」ことを表す。

遷移関数を 1 回適用することを 1 ステップと数える（$q_{\mathrm{acc}}$ や $q_{\mathrm{rej}}$ に移る遷移も 1 ステップと数える）。

$m,n$ を $m>n\ge 1$ を満たす整数とする。入力 $w=a^m{b}^n$（$a$ を $m$ 個並べた後に $b$ を $n$ 個並べた文字列）に対して $M$ を動かしたとき、$M$ が停止するまでのステップ数を $m,n$ の式で求めよ。

両側に無限に続くテープを 1 本もつ決定性チューリング機械 $M$ を考える。

• 状態の集合: $\{q_0,q_1,q_2,q_3,h\}$。初期状態は $q_0$、停止状態は $h$（$h$ からの遷移はなく、$h$ に入った時点で $M$ は停止する）
• 入力アルファベット: $\{1\}$、テープ記号の集合: $\{1,\bigsqcup \}$（$\bigsqcup$ は空白記号）
• 遷移関数 $\delta$ は次の表で与えられる。表の「(書く記号, ヘッドの移動, 次の状態)」で、$\mathrm{R}$ は右へ 1 マス、$\mathrm{L}$ は左へ 1 マス動くことを表す。

$n$ を 0 以上の整数とする。はじめ、テープには連続する $n$ マスに $1$ が書かれ（入力 $1^n$）、それ以外のマスはすべて $\bigsqcup$ である。ヘッドは入力の左端のマス（$n=0$ のときは任意の 1 マス）にあり、状態は $q_0$ である。