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

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

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

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

$N$ に部分集合構成を適用して決定性有限オートマトン $D$ をつくる。 $D$ の初期状態は ${q_{0}}$ であり、 $D$ の状態 $S$ （ $N$ の状態の部分集合）と文字 $c \in Σ$ に対して、遷移先を $q \in S ⋃ δ (q, c)$ と定める。 $D$ の状態のうち、初期状態 ${q_{0}}$ からある入力文字列（空文字列を含む）を読んで到達できるもの（到達可能な状態）の個数を求めよ。なお、空集合 $\emptyset$ も到達できる場合は 1 つの状態として数える。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

技能「部分集合構成」を使います。初期状態 ${q_{0}}$ から始め、各文字で到達しうる状態の集合を順にたどって、新しく現れる部分集合を記録していきましょう。

ヒント 2

部分集合 $S$ から文字 $c$ での遷移先は $⋃_{q \in S} δ (q, c)$ です。たとえば ${q_{0}, q_{1}}$ から $b$ を読むと $δ (q_{0}, b) \cup δ (q_{1}, b)$ になります。

ヒント 3

${q_{0}} a {q_{0}, q_{1}}$ 、 ${q_{0}, q_{1}} b {q_{0}, q_{2}}$ となります。続けて ${q_{0}, q_{2}}$ から $a$ , $b$ を読んだ先を計算し、新しい部分集合が出なくなるまで続けましょう。

答えと解説

答えを見る

4

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

解説を読む

部分集合構成では、初期状態 ${q_{0}}$ から始めて、まだ調べていない部分集合について各文字での遷移先（集合の各要素の遷移先の和集合）を計算し、新しい部分集合が出てくるたびに調べる対象に加えていきます。新しい部分集合が出てこなくなったら終わりです。

手順 1： ${q_{0}}$ から
${q_{0}} a δ (q_{0}, a) = {q_{0}, q_{1}}, {q_{0}} b δ (q_{0}, b) = {q_{0}}$
新しく ${q_{0}, q_{1}}$ が出てきました。

手順 2： ${q_{0}, q_{1}}$ から
$a : δ (q_{0}, a) \cup δ (q_{1}, a) = {q_{0}, q_{1}} \cup \emptyset = {q_{0}, q_{1}}$
$b : δ (q_{0}, b) \cup δ (q_{1}, b) = {q_{0}} \cup {q_{2}} = {q_{0}, q_{2}}$
新しく ${q_{0}, q_{2}}$ が出てきました。

手順 3： ${q_{0}, q_{2}}$ から
$a : {q_{0}, q_{1}} \cup {q_{2}} = {q_{0}, q_{1}, q_{2}}$
$b : {q_{0}} \cup {q_{2}} = {q_{0}, q_{2}}$
新しく ${q_{0}, q_{1}, q_{2}}$ が出てきました。

手順 4： ${q_{0}, q_{1}, q_{2}}$ から
$a : {q_{0}, q_{1}} \cup \emptyset \cup {q_{2}} = {q_{0}, q_{1}, q_{2}}$
$b : {q_{0}} \cup {q_{2}} \cup {q_{2}} = {q_{0}, q_{2}}$
新しい部分集合は出てきません。

どの到達可能な状態の遷移先もすでに見つかった部分集合なので、ここで構成は終わります。得られた $D$ の遷移表は次のとおりです。

$D$ の状態	$a$	$b$
${q_{0}}$	${q_{0}, q_{1}}$	${q_{0}}$
${q_{0}, q_{1}}$	${q_{0}, q_{1}}$	${q_{0}, q_{2}}$
${q_{0}, q_{2}}$	${q_{0}, q_{1}, q_{2}}$	${q_{0}, q_{2}}$
${q_{0}, q_{1}, q_{2}}$	${q_{0}, q_{1}, q_{2}}$	${q_{0}, q_{2}}$

どの状態にも $q_{0}$ が含まれ、 $δ (q_{0}, c)$ は空でないので、空集合 $\emptyset$ には到達しません。

よって、到達可能な状態は ${q_{0}}, {q_{0}, q_{1}}, {q_{0}, q_{2}}, {q_{0}, q_{1}, q_{2}}$ の $4$ 個です。

別解

部分集合構成を初期状態 ${q_{0}}$ から順に進める。

${q_{0}}$ ： $a$ で $δ (q_{0}, a) = {q_{0}, q_{1}}$ 、 $b$ で ${q_{0}}$ 。
${q_{0}, q_{1}}$ ： $a$ で ${q_{0}, q_{1}} \cup \emptyset = {q_{0}, q_{1}}$ 、 $b$ で ${q_{0}} \cup {q_{2}} = {q_{0}, q_{2}}$ 。
${q_{0}, q_{2}}$ ： $a$ で ${q_{0}, q_{1}} \cup {q_{2}} = {q_{0}, q_{1}, q_{2}}$ 、 $b$ で ${q_{0}} \cup {q_{2}} = {q_{0}, q_{2}}$ 。
${q_{0}, q_{1}, q_{2}}$ ： $a$ で ${q_{0}, q_{1}} \cup \emptyset \cup {q_{2}} = {q_{0}, q_{1}, q_{2}}$ 、 $b$ で ${q_{0}} \cup {q_{2}} \cup {q_{2}} = {q_{0}, q_{2}}$ 。

新しい状態が出なくなったので、到達可能な状態は ${q_{0}}$ , ${q_{0}, q_{1}}$ , ${q_{0}, q_{2}}$ , ${q_{0}, q_{1}, q_{2}}$ の 4 個である。空集合は、どの状態も $q_{0}$ を含み続けるため到達できない。

検算：この NFA は「 $ab$ を部分文字列として含む文字列」を受理する。入力例 $ε, a, ab, aba$ はそれぞれ ${q_{0}}, {q_{0}, q_{1}}, {q_{0}, q_{2}}, {q_{0}, q_{1}, q_{2}}$ に到達し、上の表と一致する。

答え：4

この問題の確認

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

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

確認の方法について

間違いを報告する

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

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

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

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

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