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

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

アルファベット $Σ = {a, b}$ 上の言語 $L \subseteq Σ^{*}$ を
$L = {w \in Σ^{*} ∣ w は abb で終わる}$
と定める。マイヒル・ネローデの定理を用いて、 $L$ を受理する最小の完全 DFA（すべての状態とすべての文字について遷移が定義されている決定性有限オートマトン）の状態数を求めよ。

この問題で使うもの

マイヒル・ネローデの定理と最小状態数（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

マイヒル・ネローデの定理を使います。最小 DFA の状態数は、接尾辞 $z$ で区別できない文字列の同値類の個数です。

ヒント 2

$abb$ の先頭部分 $ε, a, ab, abb$ を候補にし、各 2 つについて一方だけを $L$ に入れる接尾辞 $z$ を探しましょう。

ヒント 3

$ε$ と $a$ は $z = bb$ で、 $a$ と $ab$ は $z = b$ で区別できます。 $abb$ は $z = ε$ でほかの 3 つと区別できます。残りの組を区別し、同値類がこれ以上ないことを DFA を作って確かめましょう。

答えと解説

答えを見る

4

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

解説を読む

方針. マイヒル・ネローデの定理によれば、 $L$ を受理する最小の完全 DFA の状態数は、次の同値関係 $\equiv_{L}$ の同値類の個数に等しい。
$x \equiv_{L} y ⟺ すべての z \in Σ^{*} について (x z \in L \Leftrightarrow y z \in L)$
そこで、互いに区別できる文字列を見つけて同値類の個数の下限を出し、その個数の状態をもつ DFA を作って上限を示す。

手順 1：区別できる 4 つの文字列. 候補として $ε, a, ab, abb$ をとる。どの 2 つについても、一方だけを $L$ に入れる接尾辞 $z$ を次のように選べる。
- $ε$ と $a$ ： $z = bb$ とすると $abb \in L$ 、 $bb \in / L$ 。
- $ε$ と $ab$ ： $z = b$ とすると $abb \in L$ 、 $b \in / L$ 。
- $a$ と $ab$ ： $z = b$ とすると $abb \in L$ 、 $ab \in / L$ 。
- $ε, a, ab$ のそれぞれと $abb$ ： $z = ε$ とすると $abb \in L$ で、 $ε, a, ab \in / L$ 。

したがってこの 4 つは互いに異なる同値類に属し、同値類は少なくとも $4$ 個ある。

手順 2：4 状態の DFA で受理できる. 「読んだ文字列の末尾と $abb$ の先頭が最長で何文字一致しているか」を記憶する状態 $q_{0}$ （一致なし）、 $q_{1}$ （ $a$ ）、 $q_{2}$ （ $ab$ ）、 $q_{3}$ （ $abb$ ）をとる。初期状態を $q_{0}$ 、受理状態を $q_{3}$ とし、遷移を次のように定める。

状態	$a$	$b$
$q_{0}$	$q_{1}$	$q_{0}$
$q_{1}$	$q_{1}$	$q_{2}$
$q_{2}$	$q_{1}$	$q_{3}$
$q_{3}$	$q_{1}$	$q_{0}$

どの状態からでも $a$ を読めば末尾は $a$ になるので、 $q_{1}$ に移る。 $b$ を読んだときは、 $ab$ の後なら $abb$ になり、 $a$ の後なら $ab$ になる。それ以外（直前が一致なし、または $abb$ ）の後では、 $bb$ や $bbb$ で終わることになり $abb$ の先頭と一致しないので $q_{0}$ に移る。

この DFA は完全であり、ちょうど $abb$ で終わる文字列を受理する。同じ状態に到達する文字列どうしは同値なので、同値類は高々 $4$ 個である。

結論. 同値類の個数はちょうど $4$ である。よって最小の完全 DFA の状態数は $4$ である。

別解

Myhill–Nerode の定理より、最小の完全 DFA の状態数は、 $L$ に関する分配同値関係 $x \sim y ⟺ \forall z (x z \in L \Leftrightarrow y z \in L)$ の同値類の個数に等しい。

代表元として $ε, a, ab, abb$ を考える。これらは $L$ の「 $abb$ のどこまで一致しているか」を表す（最長の接頭辞に相当する接尾辞の長さ 0,1,2,3）。

区別可能性
- $ε$ と $abb$ ： $z = ε$ で $ε \in / L$ , $abb \in L$ なので区別できる。
- $abb$ は他の 3 つと $z = ε$ で区別される。
- $ε$ と $a$ ： $z = bb$ で $bb \in / L$ , $abb \in L$ なので区別できる。
- $ε$ と $ab$ ： $z = b$ で $b \in / L$ , $abb \in L$ なので区別できる。
- $a$ と $ab$ ： $z = b$ で $ab \in / L$ , $abb \in L$ なので、 $z = b$ で $ab \cdot b = abb \in L$ だが $a \cdot b = ab \in / L$ なので区別できる。

よって少なくとも 4 つの類がある。

4 つで尽きること
任意の語 $w$ について、 $w z \in L$ かどうかは $w$ の末尾のうち $abb$ の接頭辞と一致する最長の接尾辞のみで決まる。その長さは 0,1,2,3 のいずれかであり、それぞれ $ε, a, ab, abb$ と同値である。

DFA（状態 $q_{0}, q_{1}, q_{2}, q_{3}$ はそれぞれ $ε, a, ab, abb$ の類）

状態	a	b
$q_{0}$	$q_{1}$	$q_{0}$
$q_{1}$	$q_{1}$	$q_{2}$
$q_{2}$	$q_{1}$	$q_{3}$
$q_{3}$	$q_{1}$	$q_{0}$

初期状態は $q_{0}$ 、受理状態は $q_{3}$ 。

検算： $aabb$ は $q_{0} \to q_{1} \to q_{1} \to q_{2} \to q_{3}$ で受理される。 $abba$ は $q_{3}$ から $a$ で $q_{1}$ となり受理されない。これは正しい。

以上より、最小の完全 DFA の状態数は 4。

この問題の確認

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

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

確認の方法について

間違いを報告する

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