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

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

アルファベット $Σ = {a, b}$ 上の言語 $L$ を次のように定める。 $∣ w ∣$ は文字列 $w$ の長さを表す。
$L = {w \in Σ^{*} ∣ ∣ w ∣ を 3 で割った余りが 1 であり、かつ w は ba で終わる}$
$L$ を受理する DFA を、次の手順で作る。

$A_{1}$ ：それまでに読んだ文字列 $w$ について、 $∣ w ∣$ を $3$ で割った余り（ $0, 1, 2$ ）を状態として記憶する DFA。
$A_{2}$ ：それまでに読んだ文字列 $w$ の末尾が $ba$ の先頭部分とどこまで一致しているか、を状態として記憶する DFA。状態は、 $w$ の末尾と一致する $ba$ の先頭部分のうち最も長いものが「空文字列」「 $b$ 」「 $ba$ 」の $3$ 通りに対応する。
$A$ ： $A_{1}$ と $A_{2}$ の積構成で作った DFA。状態は $A_{1}$ の状態と $A_{2}$ の状態の組で、 $A_{1}$ のすべての状態と $A_{2}$ のすべての状態の組をすべて状態とする。各文字を読むと、組の両方の成分をそれぞれの DFA の遷移に従って同時に動かす。初期状態は両方の初期状態の組、受理状態は両方の成分が受理状態である組とする。

このとき、DFA $A$ の状態の個数を求めよ。

この問題で使うもの

言語の条件から DFA を作る（余り・接尾辞・積構成）（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

技能「言語の条件から DFA を作る（余り・接尾辞・積構成）」を使います。まず 2 つの条件それぞれについて、何を記憶すればよいか（状態）を決めましょう。

ヒント 2

$A_{1}$ は長さを $3$ で割った余り、 $A_{2}$ は末尾が $ba$ のどこまでと一致しているかを記憶します。積構成では、状態は $(A_{1} の状態, A_{2} の状態)$ の組です。

ヒント 3

$A_{1}$ の状態は $p_{0}, p_{1}, p_{2}$ の $3$ 個、 $A_{2}$ の状態は「空文字列」「 $b$ 」「 $ba$ 」に対応する $3$ 個です。あとは組の個数を積の法則で数えます。

答えと解説

答えを見る

9

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

解説を読む

手順 1： $A_{1}$ （長さの余り）を作る。
状態を $p_{0}, p_{1}, p_{2}$ とする。 $p_{r}$ は「これまでに読んだ文字列の長さを $3$ で割った余りが $r$ 」を表す。どの文字を読んでも長さは $1$ 増えるので、遷移は
$p_{0} \to p_{1}, p_{1} \to p_{2}, p_{2} \to p_{0} (文字 a, b どちらでも)$
となる。初期状態は $p_{0}$ （空文字列の長さは $0$ ）、受理状態は $p_{1}$ である。状態数は $3$ 。

手順 2： $A_{2}$ （接尾辞 $ba$ ）を作る。
状態を $q_{0}, q_{1}, q_{2}$ とし、 $q_{0}$ は末尾が $ba$ の先頭部分と一致していない（一致する最長部分が空文字列）、 $q_{1}$ は末尾が $b$ 、 $q_{2}$ は末尾が $ba$ を表す。遷移表は次のとおり。

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

（例： $q_{1}$ で $a$ を読むと末尾が $ba$ になるので $q_{2}$ 。 $q_{2}$ で $b$ を読むと末尾は $b$ なので $q_{1}$ 。）初期状態は $q_{0}$ 、受理状態は $q_{2}$ である。状態数は $3$ 。

手順 3：積構成。
$A$ の状態は組 $(p_{i}, q_{j})$ （ $i, j \in {0, 1, 2}$ ）である。 $i$ の選び方が $3$ 通り、 $j$ の選び方が $3$ 通りなので、積の法則より状態の個数は
$3 \times 3 = 9$
である。初期状態は $(p_{0}, q_{0})$ 、受理状態は $(p_{1}, q_{2})$ の $1$ つだけである。

（確認） $w = aaba$ は長さ $4$ （余り $1$ ）で $ba$ で終わるので $L$ に属する。実際に $A$ でたどると
$(p_{0}, q_{0}) a (p_{1}, q_{0}) a (p_{2}, q_{0}) b (p_{0}, q_{1}) a (p_{1}, q_{2})$
となり、受理状態で終わるので受理される。

よって、 $A$ の状態の個数は $9$ である。

別解

問題文の手順どおり、積構成の状態は $A_{1}$ の状態と $A_{2}$ の状態の組をすべて数える。 $A_{1}$ の状態は余り $0, 1, 2$ の $3$ 通り。 $A_{2}$ の状態は「空文字列」「 $b$ 」「 $ba$ 」の $3$ 通り。

問題文は「すべての状態の組をすべて状態とする」と明記しているので、初期状態から到達できない状態があっても数に含める。したがって状態数は $3 \times 3 = 9$ 。

念のため到達可能性を確かめる。初期状態は $(0, ε)$ 。 $a$ を読むと $(1, ε)$ 、 $b$ を読むと $(1, b)$ 。 $(1, b)$ から $a$ を読むと $(2, ba)$ 、 $b$ を読むと $(2, b)$ 。 $(1, ε)$ から $a$ を読むと $(2, ε)$ 。 $(2, \cdot)$ から次に読むと余り $0$ になり、 $(0, ε)$ 、 $(0, b)$ 、 $(0, ba)$ に到達できる。余り $1$ 、 $2$ についても同様に、 $ε$ 、 $b$ 、 $ba$ のすべてに到達できる。よって $9$ 個すべてが到達可能で、到達可能な状態だけで数えても答えは同じ。

$A_{2}$ の遷移は次のとおり。 $ε$ は $a$ で $ε$ 、 $b$ で $b$ に遷移する。 $b$ は $a$ で $ba$ 、 $b$ で $b$ に遷移する。 $ba$ は $a$ で $ε$ 、 $b$ で $b$ に遷移する。 $A_{2}$ の受理状態は $ba$ 。

$A$ の初期状態は $(0, ε)$ 、受理状態は $(1, ba)$ 。

答えは $9$ 。

この問題の確認

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

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

確認の方法について

間違いを報告する

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