* 状態集合 $Q = \{q_0, q_1, q_2\}$ * アルファベット $\Sigma = \{a, b\}$ * 遷移関数 $\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow 2^Q$ で、$\delta(q_0, a) = \{q_1\}$, $\delta(q_1, \epsilon) = \{q_0\}$, $\delta(q_1, b) = \{q_2\}$, $\delta(q_2, a) = \{q_1\}$ * 受理状態 $F = \{q_1\}$ (a) $\delta(q_0, b)$ を求めます。 (b) $M_2$ の状態遷移図を示します。 (c) $M_2$ が受理する言語を示します。 (d) $M_2$ と同じ言語を受理する決定性有限オートマトンを構成します。

## 問題の解答

###

1. 問題の内容

1. 空動作のある非決定性有限オートマトン $M_2$ が与えられています。

* 状態集合 $Q = \{q_0, q_1, q_2\}$

* アルファベット $\Sigma = \{a, b\}$

* 遷移関数 $\delta: Q \times (\Sigma \cup \{\epsilon\}) \rightarrow 2^Q$ で、$\delta(q_0, a) = \{q_1\}$, $\delta(q_1, \epsilon) = \{q_0\}$, $\delta(q_1, b) = \{q_2\}$, $\delta(q_2, a) = \{q_1\}$

* 受理状態 $F = \{q_1\}$

(a) $\delta(q_0, b)$ を求めます。

(b) $M_2$ の状態遷移図を示します。

(c) $M_2$ が受理する言語を示します。

(d) $M_2$ と同じ言語を受理する決定性有限オートマトンを構成します。

2. 決定性プッシュダウンオートマトン $M_3 = <Q, \Sigma, \Gamma, \delta, q_0, Z_0, F>$ において、$M_3$ の様相が $(q, ax, A\gamma Z_0)$ で、$\delta(q, a, A) = (p, AA)$ であるときの次の様相を示します。

3. 決定性有限オートマトン $M_4 = <Q, \Sigma, \delta, q_0, F>$ が与えられています。

* 状態集合 $Q = \{q_0, q_1, q_2, q_3, q_4, q_5\}$

* アルファベット $\Sigma = \{a\}$

* 遷移関数 $\delta: Q \times \Sigma \rightarrow Q$ で、$\delta(q_0, a) = q_1$, $\delta(q_1, a) = q_2$, $\delta(q_2, a) = q_3$, $\delta(q_3, a) = q_4$, $\delta(q_4, a) = q_5$, $\delta(q_5, a) = q_0$

* 受理状態 $F = \{q_0, q_2, q_4\}$

(a) $M_4$ の状態遷移図を示します。

(b) $M_4$ と同じ言語を受理する最簡形決定性有限オートマトン $M_5$ の状態遷移図を示します。

4. 以下の言語を受理するオートマトンを、決定性有限オートマトン (dfa)、非決定性有限オートマトン (nfa)、空動作のある非決定性有限オートマトン ($\epsilon$-nfa)、決定性プッシュダウンオートマトン (dpda)、非決定性プッシュダウンオートマトン (npda) の中から、構成可能なものをすべて挙げます。

(a) $L = \{w \mid w$ は末尾が $bb$ であるような語$\}$

(b) $L = \{a^n b^m \mid n \geq 1, m = 2n\}$

(c) $L = \{a^n b^m \mid n \geq 1, 3n \geq m \geq n\}$

###

2. 解き方の手順

1. (a) $\delta(q_0, b)$ について、$M_2$ の定義より、$\delta(q_0, b)$ は定義されていません。したがって、$\delta(q_0, b) = \emptyset$です。

(b) 状態遷移図は、状態をノード、遷移を矢印で表現します。

* 状態 $q_0, q_1, q_2$ をノードで表します。

* $q_0$ から $a$ で $q_1$ へ遷移する矢印を描きます。

* $q_1$ から $\epsilon$ で $q_0$ へ遷移する矢印を描きます。

* $q_1$ から $b$ で $q_2$ へ遷移する矢印を描きます。

* $q_2$ から $a$ で $q_1$ へ遷移する矢印を描きます。

* $q_1$ を二重丸で囲み、受理状態であることを示します。

* $q_0$を初期状態とします。

(c) $M_2$ が受理する言語は、受理状態 $q_1$ に到達できる文字列です。

* $q_0$ から $a$ で $q_1$ に到達できます。

* $q_1$ から $\epsilon$ で $q_0$ へ戻り、$a$ で $q_1$ に到達できます。

* $q_1$ から $b$ で $q_2$ へ行き、$a$ で $q_1$ に到達できます。

したがって、$M_2$ が受理する言語は、$a$ で始まり、$a$ または $ba$ が続く任意の文字列となります。$(a(a \cup ba)^*)$

(d) $M_2$ と同じ言語を受理する決定性有限オートマトンを構成するには、まず $M_2$ の状態遷移表を作成し、部分集合構成法を用いて決定性オートマトンを構成します。

$M_2$ は $a$ で始まり、$a$ または $ba$ が続く任意の文字列を受理します。この言語を受理する決定性有限オートマトンは、次のようになります。

* 状態集合 $Q' = \{s_0, s_1, s_2\}$

* アルファベット $\Sigma' = \{a, b\}$

* 初期状態 $s_0$

* 受理状態 $F' = \{s_1\}$

* 遷移関数 $\delta'$:

* $\delta'(s_0, a) = s_1$

* $\delta'(s_0, b) = \emptyset$

* $\delta'(s_1, a) = s_1$

* $\delta'(s_1, b) = s_2$

* $\delta'(s_2, a) = s_1$

* $\delta'(s_2, b) = \emptyset$

2. $M_3$の様相が$(q, ax, A\gamma Z_0)$であり、$\delta(q, a, A) = (p, AA)$ であるときの次の様相は、入力 $a$ を読み、スタックから $A$ を取り除き、$AA$ をプッシュするため、$(p, x, AA\gamma Z_0)$となります。

3. (a) $M_4$ の状態遷移図は、状態をノード、遷移を矢印で表現します。

* 状態 $q_0, q_1, q_2, q_3, q_4, q_5$ をノードで表します。

* $q_0$ から $a$ で $q_1$ へ遷移する矢印を描きます。

* $q_1$ から $a$ で $q_2$ へ遷移する矢印を描きます。

* $q_2$ から $a$ で $q_3$ へ遷移する矢印を描きます。

* $q_3$ から $a$ で $q_4$ へ遷移する矢印を描きます。

* $q_4$ から $a$ で $q_5$ へ遷移する矢印を描きます。

* $q_5$ から $a$ で $q_0$ へ遷移する矢印を描きます。

* $q_0, q_2, q_4$ を二重丸で囲み、受理状態であることを示します。

* $q_0$を初期状態とします。

(b) $M_4$ は、入力文字列 $a$ の個数が 3 で割って 0, 2, 4 余る場合に受理します。

$M_4$と同じ言語を受理する最簡形決定性有限オートマトン $M_5$ は、$M_4$ の状態を同値類に分割することで得られます。

この場合、$M_4$ の状態はすでに最簡形になっているため、$M_5$ は $M_4$ と同じになります。

状態遷移図は$M_4$と同じです。

4. (a) $L = \{w \mid w$ は末尾が $bb$ であるような語$\}$

* dfa, nfa, $\epsilon$-nfa で構成可能です。

末尾が $bb$ であることを記憶しておけば良いのでプッシュダウンオートマトンのスタックは不要。

* dpda, npda では構成できません。

正則言語のため、プッシュダウンオートマトンは不要です。

(b) $L = \{a^n b^m \mid n \geq 1, m = 2n\}$

* dfa, nfa, $\epsilon$-nfa では構成できません。

$a$ の個数を記憶する必要があるので、状態数が無限個必要になってしまいます。

* dpda, npda で構成可能です。

$a$ を読み込んだらスタックに積んで、$b$を読み込んだらスタックから取り出す操作をすることで、$b$の個数が$a$の個数の2倍であるか確認できます。

(c) $L = \{a^n b^m \mid n \geq 1, 3n \geq m \geq n\}$

* dfa, nfa, $\epsilon$-nfa では構成できません。

$a$ の個数を記憶する必要があるので、状態数が無限個必要になってしまいます。

* npda で構成可能です。

* dpda では構成できません。

###

3. 最終的な答え

1. (a) $\delta(q_0, b) = \emptyset$

(b) (状態遷移図は省略)

(c) $L = a(a \cup ba)^*$

(d) (決定性有限オートマトンの構成は省略)

2. $(p, x, AA\gamma Z_0)$

3. (a) (状態遷移図は省略)

(b) (状態遷移図は省略。M4と同じ)

4. (a) dfa, nfa, $\epsilon$-nfa

(b) dpda, npda

(c) npda