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

難易度 2教科書の演習問題レベル大学数学オートマトン・形式言語

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

状態 \\ 入力	$a$	$b$
$p$	${p, q}$	${p}$
$q$	${r}$	${s}$
$r$	$\emptyset$	${s}$
$s$	${s}$	$\emptyset$

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

この問題で使うもの

非決定性有限オートマトンと部分集合構成（説明と入口の問題）

この問題を解けるようになるまで（2 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

初期状態 ${p}$ から始め、各部分集合 $T$ について $a$ と $b$ での遷移先 $⋃_{t \in T} δ (t, c)$ を計算し、新しい部分集合が出なくなるまで続けよう。

ヒント 2

$p$ は $a$ でも $b$ でも $p$ 自身に遷移するので、到達できる部分集合にはいつも $p$ が入っている。空集合に到達するかどうかもこれでわかる。

ヒント 3

${p} a {p, q}$ 、 ${p, q} a {p, q, r}$ 、 ${p, q} b {p, s}$ となる。続けて ${p, s}$ などからの遷移を計算しよう。

答えと解説

答えを見る

6

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

部分集合構成では、 $D$ の状態は $N$ の状態の部分集合 $T$ で、入力 $c$ による遷移は
$δ_{D} (T, c) = t \in T ⋃ δ (t, c)$
で定める。初期状態 ${p}$ から順に遷移先を計算し、新しい部分集合が出なくなるまで続ける。

1. ${p}$ : $a \to {p, q}$ 、 $b \to {p}$
2. ${p, q}$ : $a \to {p, q} \cup {r} = {p, q, r}$ 、 $b \to {p} \cup {s} = {p, s}$
3. ${p, q, r}$ : $a \to {p, q} \cup {r} \cup \emptyset = {p, q, r}$ 、 $b \to {p} \cup {s} \cup {s} = {p, s}$
4. ${p, s}$ : $a \to {p, q} \cup {s} = {p, q, s}$ 、 $b \to {p} \cup \emptyset = {p}$
5. ${p, q, s}$ : $a \to {p, q} \cup {r} \cup {s} = {p, q, r, s}$ 、 $b \to {p} \cup {s} \cup \emptyset = {p, s}$
6. ${p, q, r, s}$ : $a \to {p, q} \cup {r} \cup \emptyset \cup {s} = {p, q, r, s}$ 、 $b \to {p} \cup {s} \cup {s} \cup \emptyset = {p, s}$

ここで新しい部分集合は現れなくなった。なお、 $p$ は $a$ でも $b$ でも自分自身に遷移するので、到達可能な部分集合はすべて $p$ を含み、 $\emptyset$ には到達しない。

よって到達可能な状態は
${p}, {p, q}, {p, q, r}, {p, s}, {p, q, s}, {p, q, r, s}$
の $6$ 個であり、 $D$ の状態数は $6$ である。

答え: $6$

別解

初期状態 ${p}$ から、各記号での遷移先の和集合を取って到達可能な部分集合を調べる。

${p}$ : $a \to {p, q}$ , $b \to {p}$
${p, q}$ : $a \to {p, q} \cup {r} = {p, q, r}$ , $b \to {p} \cup {s} = {p, s}$
${p, q, r}$ : $a \to {p, q} \cup {r} \cup \emptyset = {p, q, r}$ , $b \to {p} \cup {s} \cup {s} = {p, s}$
${p, s}$ : $a \to {p, q} \cup {s} = {p, q, s}$ , $b \to {p} \cup \emptyset = {p}$
${p, q, s}$ : $a \to {p, q} \cup {r} \cup {s} = {p, q, r, s}$ , $b \to {p} \cup {s} \cup \emptyset = {p, s}$
${p, q, r, s}$ : $a \to {p, q, r, s}$ , $b \to {p} \cup {s} \cup {s} \cup \emptyset = {p, s}$

新しい部分集合はもう現れないので、到達可能な状態は ${p}, {p, q}, {p, q, r}, {p, s}, {p, q, s}, {p, q, r, s}$ の 6 個（空集合は現れない）。受理状態は $s$ を含む ${p, s}, {p, q, s}, {p, q, r, s}$ 。

検算: 全ての遷移先が上の 6 個のどれかに入っており、 $p$ は常に含まれる（ $p$ が $a, b$ とも自身に戻るため）ことと整合する。したがって状態数は 6。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる

状態	$a$	$b$
$1$	${1}$	${1, 2}$
$2$	${3}$	${3}$
$3$	$\emptyset$	$\emptyset$

状態	$a$	$b$
$q_{0}$	${q_{0}, q_{1}}$	${q_{0}}$
$q_{1}$	$\emptyset$	${q_{2}}$
$q_{2}$	${q_{2}}$	${q_{2}}$

状態	入力 $0$	入力 $1$
$A$	${A}$	${A, B}$
$B$	${C}$	${C}$
$C$	$\emptyset$	$\emptyset$

状態	$a$	$b$
$0$	${0, 1}$	${0}$
$1$	${2}$	${2, 3}$
$2$	${3}$	$\emptyset$
$3$	$\emptyset$	$\emptyset$