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

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

アルファベット $Σ = {a, b}$ 上の文字列 $w$ について、 $w$ に含まれる $b$ の個数を $∣ w ∣_{b}$ と書く。言語 $L \subseteq Σ^{*}$ を次のように定める。
$L = {w \in Σ^{*} ∣ ∣ w ∣_{b} \equiv 2 (mod 4) かつ w は ab で終わる}$

条件「 $∣ w ∣_{b} \equiv 2 (mod 4)$ 」を判定する DFA $A_{1}$ と、条件「 $w$ は $ab$ で終わる」を判定する DFA $A_{2}$ を、それぞれ状態数が最小になるように作る。次に、 $A_{1}$ の状態と $A_{2}$ の状態の組 $(p, s)$ をすべて状態とする積構成によって、 $L$ を受理する DFA $A$ を作る。

$A$ の状態数を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

条件ごとに「何を記憶すればよいか」を決めて DFA を作り、積構成（状態の組）で共通部分の DFA を作る技能を使います。

ヒント 2

条件 (i) では $b$ の個数を $4$ で割った余りを、条件 (ii) では「末尾が $ab$ のどこまで一致しているか」（何もなし／ $a$ ／ $ab$ ）を記憶します。積構成の状態数は、2 つの DFA の状態数の積です。

ヒント 3

$A_{1}$ は余り $0, 1, 2, 3$ に対応する $4$ 状態、 $A_{2}$ は $s_{0}$ （一致なし）、 $s_{1}$ （末尾が $a$ ）、 $s_{2}$ （末尾が $ab$ ）の $3$ 状態です。あとは組の個数を数えます。

答えと解説

答えを見る

12

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

解説を読む

手順 1：条件 (i)「 $∣ w ∣_{b} \equiv 2 (mod 4)$ 」の DFA $A_{1}$ を作る。

記憶しておけばよい情報は「これまでに読んだ $b$ の個数を $4$ で割った余り」だけである。そこで、余り $0, 1, 2, 3$ に対応する状態 $r_{0}, r_{1}, r_{2}, r_{3}$ を用意する。

初期状態は $r_{0}$ （空文字列では $b$ は $0$ 個）
$a$ を読んでも $b$ の個数は変わらないので、 $r_{i} a r_{i}$
$b$ を読むと個数が $1$ 増えるので、 $r_{i} b r_{(i + 1) mod 4}$
受理状態は $r_{2}$

この 4 状態はどの 2 つも区別しなければならない。たとえば $r_{i}$ と $r_{j}$ （ $i \neq = j$ ）は、後ろに $b$ を $(2 - i) mod 4$ 個つけると、 $r_{i}$ からは $r_{2}$ （受理）に、 $r_{j}$ からは $r_{2}$ 以外（不受理）に行く。よって $A_{1}$ の最小の状態数は $4$ である。

手順 2：条件 (ii)「 $ab$ で終わる」の DFA $A_{2}$ を作る。

記憶しておけばよい情報は「 $w$ の末尾が $ab$ の先頭部分とどこまで一致しているか」である。

$s_{0}$ ：末尾が $a$ でも $ab$ でもない（空文字列を含む）
$s_{1}$ ：末尾が $a$
$s_{2}$ ：末尾が $ab$

遷移は次のとおり。

状態	$a$	$b$
$s_{0}$ （初期）	$s_{1}$	$s_{0}$
$s_{1}$	$s_{1}$	$s_{2}$
$s_{2}$ （受理）	$s_{1}$	$s_{0}$

$s_{2}$ だけが受理状態なので、 $s_{2}$ は $s_{0}, s_{1}$ と区別される。 $s_{0}$ と $s_{1}$ は、後ろに $b$ をつけると $s_{0} \to s_{0}$ （不受理）、 $s_{1} \to s_{2}$ （受理）となるので区別される。よって $A_{2}$ の最小の状態数は $3$ である。

手順 3：積構成で $A$ を作る。

$A$ の状態は組 $(r_{i}, s_{j})$ で、 $1$ 文字読むごとに両方の成分を同時に遷移させる。たとえば $(r_{i}, s_{j}) b (r_{(i + 1) mod 4}, δ_{2} (s_{j}, b))$ である。初期状態は $(r_{0}, s_{0})$ 、受理状態は両方の条件を満たす $(r_{2}, s_{2})$ のみである。

状態の組の個数は、積の法則より
$4 \times 3 = 12$
である。

したがって、 $A$ の状態数は $12$ である。

別解

$A_{1}$ （最小 DFA）: 状態は $b$ の個数を 4 で割った余り $0, 1, 2, 3$ の 4 個。初期状態は $0$ 、受理状態は $2$ 。遷移は $a$ では状態を変えず、 $b$ では $p \mapsto p + 1 (mod 4)$ とする。
状態 $i, j$ ( $i \neq = j$ ) は、接尾辞 $b^{k}$ を $k \equiv 2 - i (mod 4)$ とすると、 $i$ からは受理されるが $j$ からは受理されない。よって 4 状態はすべて区別でき、最小は 4 状態である。

$A_{2}$ （最小 DFA）: 状態は $q_{0}$ （直前が $a$ でなく、 $ab$ の途中でもない。初期状態）、 $q_{1}$ （直前の文字が $a$ ）、 $q_{2}$ （ $ab$ で終わっている）の 3 個。受理状態は $q_{2}$ 。

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

区別可能性は次のとおり。 $q_{2}$ だけが受理状態なので、 $q_{2}$ は他と区別できる。 $q_{0}$ と $q_{1}$ は、文字列 $b$ を読むと $q_{0} \to q_{0}$ （非受理）、 $q_{1} \to q_{2}$ （受理）となるので区別できる。したがって最小は 3 状態である。

積構成: 問題文の指定により、状態集合は ${0, 1, 2, 3} \times {q_{0}, q_{1}, q_{2}}$ のすべての組である。到達可能かどうかで数を減らさない。
初期状態は $(0, q_{0})$ 、受理状態は $(2, q_{2})$ 。遷移は成分ごとに $δ ((p, s), c) = (δ_{1} (p, c), δ_{2} (s, c))$ とする。
状態数は $4 \times 3 = 12$ 。

検算: 到達可能性を確かめると、 $(0, q_{0})$ から $a$ で $(0, q_{1})$ 、 $ab$ で $(1, q_{2})$ 、 $b$ で $(1, q_{0})$ などと進み、12 個すべてに到達できる。よって到達不能状態を除いても 12 個で、答えは変わらない。

この問題の確認

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

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

確認の方法について

間違いを報告する

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