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

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

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

アルファベット $Σ = {a, b}$ 上の言語 $L \subseteq Σ^{*}$ を次のように定めます。
$L = {w \in Σ^{*} ∣ ∣ w ∣ \geq 2 かつ w の後ろから 2 文字目が a}$
たとえば $aa, ab, bab \in L$ であり、 $ε, a, ba, abb \in / L$ です。

$L$ を受理する完全な決定性有限オートマトン（DFA）のうち、状態数が最小のものの状態数を求めてください。ここで完全な DFA とは、すべての状態とすべての文字に対して遷移が定義されている DFA のことです。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

マイヒル・ネローデの定理を使います。接尾辞 $z$ を付けたときに $L$ に入るかどうかが食い違う文字列の組を探し、同値類の個数を数えましょう。

ヒント 2

$x z \in L$ かどうかは $x z$ の後ろから 2 文字目で決まります。 $x$ の情報のうち、最後の 2 文字だけが効くことに注目しましょう。

ヒント 3

代表の候補は $aa, ab, ba, bb$ です。 $ε$ と $b$ は $bb$ と同値になり、 $a$ は $ba$ と同値になります。あとは、4 つの候補がどの 2 つも接尾辞（ $ε$ または $a$ ）で区別できるかを確かめます。

答えと解説

答えを見る

4

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

解説を読む

マイヒル・ネローデの定理を使います。文字列 $x, y$ について、すべての $z \in Σ^{*}$ で「 $x z \in L ⟺ y z \in L$ 」が成り立つとき $x \equiv_{L} y$ と書きます。最小の完全 DFA の状態数は、この同値関係 $\equiv_{L}$ の同値類の個数に等しくなります。

手順 1：同値類の代表の候補を挙げる

$x z \in L$ となるかどうかは、 $x z$ の後ろから 2 文字目だけで決まります。 $∣ z ∣ \geq 2$ ならこの文字は $z$ の中にあるので、 $x$ には関係しません。 $∣ z ∣ \leq 1$ のときは、 $x$ の最後の 2 文字だけが関係します。そこで、長さ 2 の文字列 $aa, ab, ba, bb$ を代表の候補とします。

手順 2：どの文字列も 4 つの候補のどれかと同値であることを確かめる

$∣ w ∣ \geq 2$ のとき、 $w$ は自身の最後の 2 文字からなる文字列と同値です。手順 1 で見たように、どの $z$ についても判定に効くのは $w$ の最後の 2 文字だけだからです。
$ε \equiv_{L} bb$ です。
$∣ z ∣ \geq 2$ なら、 $z$ と $bb z$ の後ろから 2 文字目は一致します。
$∣ z ∣ = 1$ なら、 $z \in / L$ （長さ 1）であり、 $bb z$ の後ろから 2 文字目は $b$ なので $bb z \in / L$ です。
$∣ z ∣ = 0$ なら、 $ε \in / L$ かつ $bb \in / L$ です。
$a \equiv_{L} ba$ です。
$∣ z ∣ \geq 2$ なら、上と同じ理由で判定は一致します。
$∣ z ∣ = 1$ なら、 $a z$ と $ba z$ の後ろから 2 文字目はどちらも $a$ なので、ともに $L$ に属します。
$∣ z ∣ = 0$ なら、 $a \in / L$ かつ $ba \in / L$ です。
$b \equiv_{L} bb$ です。 $b$ も $bb$ も「直前の文字が $b$ で、それより前に $a$ が効かない」状態だからで、確認の仕方は $ε \equiv_{L} bb$ の場合と同じです。

したがって、同値類は高々 4 個です。

手順 3：4 つの候補がどの 2 つも区別できることを示す

各組について、 $x z$ と $y z$ の一方だけが $L$ に属するような接尾辞 $z$ を挙げます。

組	$z$	判定
$aa, ab$	$a$	$aaa \in L, aba \in / L$
$aa, ba$	$ε$	$aa \in L, ba \in / L$
$aa, bb$	$ε$	$aa \in L, bb \in / L$
$ab, ba$	$ε$	$ab \in L, ba \in / L$
$ab, bb$	$ε$	$ab \in L, bb \in / L$
$ba, bb$	$a$	$baa \in L, bba \in / L$

よって 4 つの候補は互いに同値ではなく、同値類はちょうど 4 個です。

結論

マイヒル・ネローデの定理より、 $L$ を受理する最小の完全 DFA の状態数は $4$ です。

別解

$L$ は「後ろから 2 文字目が $a$ 」という言語である。状態を「直前の 2 文字」で表す DFA を作り、状態数が 4 で最小であることを Myhill–Nerode の定理で示す。

DFA（状態数 4）
状態を $q_{x y}$ とする。これは「最後の 2 文字が $x y$ 」を表す。長さ 2 未満の入力は、足りない部分を $b$ とみなす。つまり $ε \sim bb$ 、 $a \sim ba$ 、 $b \sim bb$ とする。
- 状態集合は ${q_{aa}, q_{ab}, q_{ba}, q_{bb}}$
- 初期状態は $q_{bb}$
- 受理状態は $q_{aa}, q_{ab}$ （後ろから 2 文字目が $a$ の状態）

遷移は、状態 $q_{x y}$ で文字 $c$ を読むと $q_{y c}$ に移る。

状態	a	b
$q_{aa}$	$q_{aa}$	$q_{ab}$
$q_{ab}$	$q_{ba}$	$q_{bb}$
$q_{ba}$	$q_{aa}$	$q_{ab}$
$q_{bb}$	$q_{ba}$	$q_{bb}$

最小性（Myhill–Nerode）
4 つの文字列 $aa, ab, ba, bb$ が互いに区別できることを示す。
- 接尾辞 $ε$ を付けると、 $aa, ab \in L$ であり $ba, bb \in / L$ 。よって ${aa, ab}$ と ${ba, bb}$ は区別できる。
- 接尾辞 $a$ を付けると、 $aaa \in L$ であり $aba \in / L$ 。よって $aa$ と $ab$ は区別できる。
- 同じく接尾辞 $a$ で、 $baa \in L$ であり $bba \in / L$ 。よって $ba$ と $bb$ は区別できる。

したがって同値類は少なくとも 4 つある。上の DFA は 4 状態で $L$ を受理するので、最小の状態数は 4 である。

検算
- $ab$ ： $q_{bb} \to q_{ba} \to q_{ab}$ で受理される。
- $ba$ ： $q_{bb} \to q_{ba}$ で受理されない。
- $abb$ ： $q_{bb} \to q_{ba} \to q_{ab} \to q_{bb}$ で受理されない。
- $bab$ ： $q_{bb} \to q_{ba} \to q_{aa} \to q_{ab}$ で受理される。

どれも問題文の例と一致する。

答え：4

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題