(a) Q と Σ の直積 Q × Σ を求めます。 (b) Q のべき集合 2^Q を求めます。

## 問題の回答

###

1. 問題の内容

1. Q = {p, q, r}、Σ = {0, 1}のとき、以下の問いに答えます。

(a) Q と Σ の直積 Q × Σ を求めます。

(b) Q のべき集合 2^Q を求めます。

2. 決定性有限オートマトン M1 = (Q, Σ, δ, q0, F) が与えられています。ここで、

Q = {r, s, t}, Σ = {a, b}, δ(r, a) = s, δ(r, b) = r, δ(s, a) = t, δ(s, b) = r, δ(t, a) = t, δ(t, b) = r, q0 = r, F = {t} です。

(a) オートマトン M1 の初期状態を示します。

(b) オートマトン M1 の受理状態を示します。

(c) オートマトン M1 の状態遷移図を示します。

(d) オートマトン M1 に入力記号列 abaa が与えられたときの初期様相を示します。

(e) 入力記号列 abaa の最初の入力記号を読んだ後の様相を示します。

(f) 入力記号列 abaa をすべて読み終わるまでの様相のステップをvdashを用いて示します。

(g) 入力記号列 abaa はオートマトン M1 によって受理されるか、拒否されるか述べます。

(h) オートマトン M1 が受理する言語を示します。

###

2. 解き方の手順

1. (a) 直積 Q × Σ は、Q の要素と Σ の要素のすべての組み合わせからなる集合です。

(b) べき集合 2^Q は、Q のすべての部分集合からなる集合です。

2. (a) 初期状態は q0 = r です。

(b) 受理状態は F = {t} です。

(c) 状態遷移図は、状態をノード、遷移を入力でラベル付けされた矢印で表します。遷移関数δに基づいて図を描きます。

(d) 初期様相は、初期状態と入力記号列の組み合わせです。したがって、初期様相は (r, abaa) です。

(e) 最初の入力記号 a を読んだ後の様相は、状態遷移関数 δ(r, a) = s によって決定されます。したがって、様相は (s, baa) です。

(f) すべての様相のステップは以下のとおりです。

(r, abaa) $\vdash$ (s, baa) $\vdash$ (r, aa) $\vdash$ (s, a) $\vdash$ (t, ε)

(g) 最終状態は t であり、受理状態の集合 F = {t} に含まれるため、入力記号列 abaa はオートマトン M1 によって受理されます。

(h) オートマトン M1 が受理する言語は、状態 t に到達するすべての入力記号列の集合です。状態遷移を調べると、t に到達するには、最後に a を読んで状態 s にいる必要があります。状態 s に到達するには、r から a を読むか、s から b を読む必要があります。

###

3. 最終的な答え

1. (a) Q × Σ = {(p, 0), (p, 1), (q, 0), (q, 1), (r, 0), (r, 1)}

(b) 2^Q = { {}, {p}, {q}, {r}, {p, q}, {p, r}, {q, r}, {p, q, r} }

2. (a) r

(b) t

(c) (状態遷移図はテキストで表現するのが難しいので省略)

(d) (r, abaa)

(e) (s, baa)

(f) (r, abaa) $\vdash$ (s, baa) $\vdash$ (r, aa) $\vdash$ (s, a) $\vdash$ (t, ε)

(g) 受理される

(h) { w | w は a で終わる文字列。ただし、wは {a, b} 上の文字列}