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

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

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

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

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

$M$ と同じ言語を受理する DFA のうち、状態数が最小のもの（最小 DFA）の状態数を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

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

ヒント 2

最初に、受理状態と非受理状態からなる対すべてに印をつける。そのあと、対 ${p, q}$ について、ある入力 $c$ での遷移先の対 ${δ (p, c), δ (q, c)}$ に印があれば、 ${p, q}$ にも印をつける。これを新しい印が増えなくなるまで繰り返す。

ヒント 3

$F$ は到達不能なので除く。受理状態 ${A, D}$ と非受理状態 ${B, C, E}$ の間の 6 対に印をつけると、残りは ${A, D}, {B, C}, {B, E}, {C, E}$ になる。たとえば ${B, C}$ は、入力 $1$ で印のある ${C, D}$ に移る。

答えと解説

答えを見る

3

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

解説を読む

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

初期状態 $A$ から遷移をたどる。
- $A$ から $D, B$ に行ける。
- $D$ から $A, E$ に、 $B$ から $E, C$ に行ける。
- $C$ から $C, D$ に、 $E$ から $B, C$ に行ける。

よって、到達できる状態は ${A, B, C, D, E}$ である。 $F$ へ入る遷移は $F$ 自身からのもの（ $δ (F, 1) = F$ ）しかないので、 $F$ には到達できない。 $F$ を取り除いても受理する言語は変わらない。

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

受理状態は ${A, D}$ 、非受理状態は ${B, C, E}$ である。空文字列 $ε$ で区別できるので、次の 6 個の対に印をつける。
${A, B}, {A, C}, {A, E}, {D, B}, {D, C}, {D, E}$
印のついていない対は ${A, D}, {B, C}, {B, E}, {C, E}$ の 4 個である。

手順 3：遷移先の対に印があれば印をつける（1 巡目）。

${A, D}$ ：入力 $0$ で ${D, A}$ 、入力 $1$ で ${B, E}$ 。どちらも印なしなので、まだ印をつけない。
${B, C}$ ：入力 $1$ で ${C, D}$ 。これには印があるので、 ${B, C}$ に印をつける。
${B, E}$ ：入力 $0$ で ${E, B}$ （印なし）、入力 $1$ で ${C, C}$ （同じ状態）。印をつけない。
${C, E}$ ：入力 $1$ で ${D, C}$ 。これには印があるので、 ${C, E}$ に印をつける。

手順 4：新しい印が増えなくなるまで繰り返す（2 巡目）。

残っているのは ${A, D}$ と ${B, E}$ である。
- ${A, D}$ ：遷移先は ${D, A}$ と ${B, E}$ で、どちらも印なし。
- ${B, E}$ ：遷移先は ${E, B}$ と ${C, C}$ で、印なし。

新しい印は増えないので、ここで終了する。

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

最後まで印のつかなかった対 ${A, D}$ と ${B, E}$ は同値である。よって、同値類は
${A, D}, {B, E}, {C}$
の 3 個になる。同値類どうしは区別可能なので、これ以上まとめられない。

したがって、最小 DFA の状態数は $3$ である。（この DFA は、入力に含まれる $1$ の個数を $3$ で割った余りが $0$ である文字列を受理している。）

別解

初期状態 $A$ から到達可能な状態を調べる。 $A \to D, B$ 、 $D \to A, E$ 、 $B \to E, C$ 、 $E \to B, C$ 、 $C \to C, D$ より、到達可能なのは $A, B, C, D, E$ で、 $F$ は到達不能なので除く。

次に分割の細分化を行う（状態同値性の判定）。
- 初期分割：受理 ${A, D}$ 、非受理 ${B, C, E}$ 。
- 非受理側を見る。 $B$ ： $0 \to E$ （非受理）、 $1 \to C$ （非受理）。 $C$ ： $0 \to C$ （非受理）、 $1 \to D$ （受理）。 $E$ ： $0 \to B$ （非受理）、 $1 \to C$ （非受理）。 $C$ だけ入力 1 で受理側に行くので、 $C$ は $B, E$ と区別される。分割は ${A, D}, {B, E}, {C}$ となる。
- 受理側を見る。 $A$ ： $0 \to D$ 、 $1 \to B$ 。 $D$ ： $0 \to A$ 、 $1 \to E$ 。 $0$ では両方 ${A, D}$ 、 $1$ では両方 ${B, E}$ に行くので区別されない。
- $B, E$ を見る。 $B$ ： $0 \to E$ 、 $1 \to C$ 。 $E$ ： $0 \to B$ 、 $1 \to C$ 。 $0$ では両方 ${B, E}$ 、 $1$ では両方 ${C}$ に行くので区別されない。

分割は安定したので、同値類は ${A, D}, {B, E}, {C}$ の 3 つ。

検算： $C$ は入力 1 で受理状態 $D$ に行くので、空語以外にも $C$ から受理される語がある（死状態ではない）。 $A$ は空語を受理するが、 $B$ と $E$ は受理しない。よって 3 状態は互いに区別でき、最小 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}$

状態	$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$
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{2}$	$q_{0}$
$q_{2}$	$q_{1}$	$q_{2}$

状態	入力 $0$	入力 $1$
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{0}$	$q_{2}$
$q_{2}$	$q_{2}$	$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$	$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$