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

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

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

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

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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

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

ヒント 2

最初に「受理状態と非受理状態の対」に印をつける。次に、印のない対 ${p, q}$ について、ある文字 $x$ での行き先 ${δ (p, x), δ (q, x)}$ に印があれば ${p, q}$ にも印をつける。これを新しい印がつかなくなるまで繰り返す。

ヒント 3

状態 $6$ は到達不能なので除く。受理状態は ${3, 4}$ である。非受理状態どうしの対のうち、 ${0, 1}, {0, 5}, {1, 2}, {2, 5}$ は文字 $b$ で読むと印のついた対に移るので印がつく。残りの印のない対からできる同値類を数えよう。

答えと解説

答えを見る

3

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

解説を読む

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

初期状態 $0$ から遷移をたどる。
- $0$ から $a$ で $1$ 、 $b$ で $2$ 。
- $1$ から $1, 3$ 、 $2$ から $5, 0$ 。
- $3$ から $1, 2$ 、 $5$ から $1, 4$ 。
- $4$ から $5, 0$ 。

よって到達可能な状態は ${0, 1, 2, 3, 4, 5}$ であり、状態 $6$ にはどの状態からも遷移してこないので到達不能である。 $6$ は受理される言語に影響しないので取り除く。

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

受理状態は $F = {3, 4}$ 、非受理状態は ${0, 1, 2, 5}$ 。空文字列 $ε$ で区別できるので、 $F$ の状態と非受理状態の対
${0, 3}, {0, 4}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 5}, {4, 5}$
の 8 対に印をつける。

手順 3：印のない対を調べる。

印のない対 ${p, q}$ について、ある文字 $x$ での行き先の対 ${δ (p, x), δ (q, x)}$ に印がついていれば ${p, q}$ にも印をつける。
- ${0, 1}$ ： $b$ で ${2, 3}$ （印あり）→ 印をつける。
- ${0, 5}$ ： $b$ で ${2, 4}$ （印あり）→ 印をつける。
- ${1, 2}$ ： $b$ で ${3, 0}$ （印あり）→ 印をつける。
- ${2, 5}$ ： $b$ で ${0, 4}$ （印あり）→ 印をつける。
- ${0, 2}$ ： $a$ で ${1, 5}$ 、 $b$ で ${2, 0}$ （どちらも印なし）→ 保留。
- ${1, 5}$ ： $a$ で ${1, 1}$ （同じ状態）、 $b$ で ${3, 4}$ （印なし）→ 保留。
- ${3, 4}$ ： $a$ で ${1, 5}$ 、 $b$ で ${2, 0}$ （どちらも印なし）→ 保留。

もう一度、保留した対を調べる。行き先の対は ${1, 5}, {0, 2}, {3, 4}$ およびそれ自身の同じ状態だけで、どれにも印がついていない。新しく印がつく対はないので手続きは終了する。

手順 4：同値な状態をまとめる。

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

（確認：この 3 つのクラスを 1 つの状態とみなすと、 ${0, 2}$ は $a$ で ${1, 5}$ 、 $b$ で ${0, 2}$ ； ${1, 5}$ は $a$ で ${1, 5}$ 、 $b$ で ${3, 4}$ ； ${3, 4}$ は $a$ で ${1, 5}$ 、 $b$ で ${0, 2}$ となり、遷移がきちんと定まる。これは「 $ab$ で終わる文字列」を受理する DFA である。）

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

別解

初期状態 0 から到達可能な状態を調べる。0→1,2、1→1,3、2→5,0、3→1,2、5→1,4、4→5,0 なので、到達可能な状態は {0,1,2,3,4,5} である。状態 6 は到達不能なので除く。受理状態は 3,4 である。

分割細分（テーブル充填法）を行う。
初めの分割は {0,1,2,5}（非受理）と {3,4}（受理）。
非受理状態の遷移先は次のとおり。
- 0: a→1(非), b→2(非)
- 2: a→5(非), b→0(非)
- 1: a→1(非), b→3(受)
- 5: a→1(非), b→4(受)
よって {0,2} と {1,5} に分かれる。

分割 {0,2},{1,5},{3,4} について確認する。
- 0: a→1∈{1,5}, b→2∈{0,2}。2: a→5∈{1,5}, b→0∈{0,2}。同じクラスに移るので分かれない。
- 1: a→1∈{1,5}, b→3∈{3,4}。5: a→1∈{1,5}, b→4∈{3,4}。同じ。
- 3: a→1∈{1,5}, b→2∈{0,2}。4: a→5∈{1,5}, b→0∈{0,2}。同じ。
これ以上分割できないので、最小 DFA の状態数は 3 である。

状態	入力 $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}$

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

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

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

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題

状態	$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$	${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$