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

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

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

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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

部分集合構成を使います。初期状態 ${1}$ から始めて、現れた状態の集合ごとに $a$ と $b$ での遷移先を計算していきましょう。

ヒント 2

集合 $S$ の文字 $x$ による遷移先は $⋃_{q \in S} δ (q, x)$ です。新しい集合が出てこなくなるまで続けます。

ヒント 3

${1}$ から $a$ で ${1}$ 、 $b$ で ${1, 2}$ に移ります。 ${1, 2}$ からは $a$ で ${1, 3}$ 、 $b$ で ${1, 2, 3}$ に移ります。残りの集合についても同じように計算してみましょう。

答えと解説

答えを見る

4

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

解説を読む

部分集合構成では、 $D$ の状態は $N$ の状態の集合 $S$ であり、文字 $x$ による遷移先は
$δ_{D} (S, x) = q \in S ⋃ δ (q, x)$
で定める。初期状態 ${1}$ から始めて、新しく現れた集合について $a$ , $b$ での遷移先を順に計算していく。

${1}$ から
- $a$ : $δ (1, a) = {1}$ より ${1}$
- $b$ : $δ (1, b) = {1, 2}$ より ${1, 2}$ （新しい集合）

${1, 2}$ から
- $a$ : $δ (1, a) \cup δ (2, a) = {1} \cup {3} = {1, 3}$ （新しい集合）
- $b$ : $δ (1, b) \cup δ (2, b) = {1, 2} \cup {3} = {1, 2, 3}$ （新しい集合）

${1, 3}$ から
- $a$ : ${1} \cup \emptyset = {1}$
- $b$ : ${1, 2} \cup \emptyset = {1, 2}$

${1, 2, 3}$ から
- $a$ : ${1} \cup {3} \cup \emptyset = {1, 3}$
- $b$ : ${1, 2} \cup {3} \cup \emptyset = {1, 2, 3}$

これ以上新しい集合は現れないので、計算は終わる。どの集合も状態 $1$ を含み、 $δ (1, a)$ , $δ (1, b)$ はともに $1$ を含むので、空集合 $\emptyset$ は現れない。

よって到達可能な状態は ${1}, {1, 2}, {1, 3}, {1, 2, 3}$ の $4$ 個である（受理状態は $3$ を含む ${1, 3}$ と ${1, 2, 3}$ ）。

答え: $4$

別解

初期状態 ${1}$ から部分集合構成で到達可能な状態を調べる。

${1}$ : $a \to δ (1, a) = {1}$ 、 $b \to δ (1, b) = {1, 2}$
${1, 2}$ : $a \to δ (1, a) \cup δ (2, a) = {1} \cup {3} = {1, 3}$ 、 $b \to {1, 2} \cup {3} = {1, 2, 3}$
${1, 3}$ : $a \to {1} \cup \emptyset = {1}$ 、 $b \to {1, 2} \cup \emptyset = {1, 2}$
${1, 2, 3}$ : $a \to {1} \cup {3} \cup \emptyset = {1, 3}$ 、 $b \to {1, 2} \cup {3} \cup \emptyset = {1, 2, 3}$

新しい状態は出てこないので、到達可能な状態は ${1}, {1, 2}, {1, 3}, {1, 2, 3}$ の 4 個である。状態 1 は常に保たれるため、空集合には到達しない。

検算：1 を含まない集合には到達しない（どの遷移でも $δ (1, \cdot)$ が 1 を含むため）ので、可能な状態は 1 を含む 4 個の部分集合以内であり、すべて到達可能であることを上で確認した。

答え：4

この問題の確認

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

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

確認の方法について

間違いを報告する

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

状態 \\ 入力	$a$	$b$
$p$	${p, q}$	${p}$
$q$	${r}$	${s}$
$r$	$\emptyset$	${s}$
$s$	${s}$	$\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$

状態	入力 $0$	入力 $1$
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{2}$	$q_{0}$
$q_{2}$	$q_{1}$	$q_{2}$

状態	入力 $0$	入力 $1$
$A$	$B$	$A$
$B$	$C$	$A$
$C$	$C$	$B$