この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

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

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

アルファベット $Σ = {a, b}$ 上の決定性有限オートマトン（DFA） $M$ を考える。状態の集合は ${q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}}$ 、初期状態は $q_{0}$ 、受理状態は $q_{2}$ と $q_{5}$ の 2 つである。遷移関数 $δ$ は次の表で与えられる。

状態	入力 $a$	入力 $b$
$q_{0}$	$q_{1}$	$q_{3}$
$q_{1}$	$q_{4}$	$q_{2}$
$q_{2}$	$q_{2}$	$q_{2}$
$q_{3}$	$q_{1}$	$q_{0}$
$q_{4}$	$q_{1}$	$q_{2}$
$q_{5}$	$q_{2}$	$q_{0}$

$M$ が受理する言語と同じ言語を受理する DFA のうち、状態数が最小のもの（最小 DFA）の状態数を求めよ。ただし、DFA の遷移関数はすべての状態と入力文字について定義されているものとする。

この問題で使うもの

DFA の最小化（区別可能な状態の対）（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

DFA の最小化の技能を使います。まず初期状態から到達できない状態を取り除き、そのあと区別可能な状態の対に表で印をつけていきます。

ヒント 2

受理状態と非受理状態の対には、最初に印をつけます。印のない対 ${p, q}$ は、ある入力文字 $c$ で ${δ (p, c), δ (q, c)}$ が印つきの対になるときに印をつけます。これを新しい印がつかなくなるまでくり返します。

ヒント 3

$q_{5}$ は到達不能なので除きます。受理状態 $q_{2}$ と、 $q_{0}, q_{1}, q_{3}, q_{4}$ のそれぞれとの対に印をつけます。次に入力 $b$ の遷移先を見ると、 ${q_{0}, q_{1}}$ 、 ${q_{0}, q_{4}}$ 、 ${q_{1}, q_{3}}$ 、 ${q_{3}, q_{4}}$ に印がつきます。残る対を確かめましょう。

答えと解説

答えを見る

3

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

解説を読む

手順 1：到達不能な状態を除く。

初期状態 $q_{0}$ から遷移をたどる。

$q_{0}$ から $q_{1}, q_{3}$ に行ける。
$q_{1}$ から $q_{4}, q_{2}$ に行ける。
$q_{3}$ から $q_{1}, q_{0}$ に行ける。
$q_{4}$ から $q_{1}, q_{2}$ に行ける。
$q_{2}$ からは $q_{2}$ にしか行けない。

よって到達可能な状態は ${q_{0}, q_{1}, q_{2}, q_{3}, q_{4}}$ である。 $q_{5}$ にはどの状態からも遷移が入ってこないので到達不能であり、取り除く。 $q_{5}$ は受理状態だが、どの入力でも到達しないので、取り除いても受理する言語は変わらない。

残る状態のうち受理状態は $q_{2}$ だけである。

手順 2：受理状態と非受理状態の対に印をつける。

空文字列 $ε$ で区別できるので、次の 4 対に印をつける。
${q_{2}, q_{0}}, {q_{2}, q_{1}}, {q_{2}, q_{3}}, {q_{2}, q_{4}}$

手順 3：印のない対を調べ、遷移先が印つきの対になるものに印をつける。

印のない対は、非受理状態 $q_{0}, q_{1}, q_{3}, q_{4}$ どうしの 6 対である。各対について、入力 $a, b$ での遷移先の対を調べる。

${q_{0}, q_{1}}$ ： $b$ で ${q_{3}, q_{2}}$ に移る。これは印つきなので印をつける。
${q_{0}, q_{3}}$ ： $a$ で ${q_{1}, q_{1}}$ 、 $b$ で ${q_{3}, q_{0}}$ に移る。どちらも印つきではないので保留する。
${q_{0}, q_{4}}$ ： $b$ で ${q_{3}, q_{2}}$ に移る。印つきなので印をつける。
${q_{1}, q_{3}}$ ： $b$ で ${q_{2}, q_{0}}$ に移る。印つきなので印をつける。
${q_{1}, q_{4}}$ ： $a$ で ${q_{4}, q_{1}}$ 、 $b$ で ${q_{2}, q_{2}}$ に移る。どちらも印つきではないので保留する。
${q_{3}, q_{4}}$ ： $b$ で ${q_{0}, q_{2}}$ に移る。印つきなので印をつける。

手順 4：新しい印がつかなくなるまでくり返す。

残った対を調べ直す。

${q_{0}, q_{3}}$ の遷移先は ${q_{1}, q_{1}}$ と ${q_{3}, q_{0}}$ （自分自身）である。
${q_{1}, q_{4}}$ の遷移先は ${q_{4}, q_{1}}$ （自分自身）と ${q_{2}, q_{2}}$ である。

どちらにも新しい印はつかないので、ここで終了する。

手順 5：同値類をまとめる。

印のつかなかった対 ${q_{0}, q_{3}}$ と ${q_{1}, q_{4}}$ は区別できない（同値な）状態の対である。よって同値類は
${q_{0}, q_{3}}, {q_{1}, q_{4}}, {q_{2}}$
の 3 つになる。

（参考： $M$ は「 $ab$ を部分文字列として含む文字列」を受理しており、3 つの同値類はそれぞれ「まだ $a$ を読んでいない」「直前が $a$ 」「 $ab$ を読み終えた」に対応する。）

したがって、最小 DFA の状態数は $3$ である。

別解

初期状態 $q_{0}$ から到達できる状態を調べる。 $q_{0} \to q_{1}, q_{3}$ 、 $q_{1} \to q_{4}, q_{2}$ 、 $q_{3} \to q_{1}, q_{0}$ 、 $q_{4} \to q_{1}, q_{2}$ で、 $q_{2}$ は自分自身に戻る。よって到達可能な状態は $q_{0}, q_{1}, q_{2}, q_{3}, q_{4}$ で、 $q_{5}$ は到達不能なので除く。

受理状態は到達可能なものでは $q_{2}$ のみである。 $q_{2}$ は $a, b$ のどちらでも $q_{2}$ に戻る受理の吸収状態なので、他の状態とは区別できる。

残りの $q_{0}, q_{1}, q_{3}, q_{4}$ を分割する。
- $q_{1}$ と $q_{4}$ は、 $b$ でともに $q_{2}$ へ行き、 $a$ では互いに移り合う。区別できないので同値である。
- $q_{0}$ と $q_{3}$ は、 $a$ でともに $q_{1}$ へ行き、 $b$ では互いに移り合う。区別できないので同値である。
- $q_{0}$ と $q_{1}$ は、入力 $b$ で $q_{3}$ （非受理）と $q_{2}$ （受理）に分かれるので区別できる。

分割 ${q_{0}, q_{3}}, {q_{1}, q_{4}}, {q_{2}}$ は遷移について閉じていることを確認した。
- ${q_{0}, q_{3}}$ ： $a \to {q_{1}, q_{4}}$ 、 $b \to {q_{0}, q_{3}}$
- ${q_{1}, q_{4}}$ ： $a \to {q_{1}, q_{4}}$ 、 $b \to {q_{2}}$
- ${q_{2}}$ ： $a, b \to {q_{2}}$

したがって最小 DFA の状態数は 3 である。

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$

状態	入力 $0$	入力 $1$
$A$	$D$	$B$
$B$	$E$	$C$
$C$	$C$	$D$
$D$	$A$	$E$
$E$	$B$	$C$
$F$	$A$	$F$

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

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$

状態	$a$	$b$
$0$	$1$	$2$
$1$	$1$	$3$
$2$	$5$	$0$
$3$	$1$	$2$
$4$	$5$	$0$
$5$	$1$	$4$
$6$	$6$	$6$