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

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

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

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

状態	入力 $0$	入力 $1$
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{0}$	$q_{2}$
$q_{2}$	$q_{2}$	$q_{2}$

$Σ$ 上の長さ $8$ の文字列（全部で $2^{8} = 256$ 個）のうち、 $M$ に受理されるものの個数を求めよ。

この問題で使うもの

状態ごとの文字列数の漸化式（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

技能「状態ごとの文字列数の漸化式」を使う。長さ $k$ の文字列を読み終えたとき各状態にいる個数 $N_{k} (q)$ を、 $k = 0$ から 1 文字ずつ更新していこう。

ヒント 2

遷移表から各状態に入る矢印を集めると、 $N_{k + 1} (q_{0}) = N_{k} (q_{0}) + N_{k} (q_{1})$ , $N_{k + 1} (q_{1}) = N_{k} (q_{0})$ , $N_{k + 1} (q_{2}) = N_{k} (q_{1}) + 2 N_{k} (q_{2})$ となる。初期値は $(N_{0} (q_{0}), N_{0} (q_{1}), N_{0} (q_{2})) = (1, 0, 0)$ 。

ヒント 3

順に計算すると $k = 4$ で $(5, 3, 8)$ 、 $k = 6$ で $(13, 8, 43)$ となる。あと 2 回更新して、受理状態 $q_{0}, q_{1}$ の個数を足せばよい。

答えと解説

答えを見る

55

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

解説を読む

長さ $k$ の文字列のうち、初期状態 $q_{0}$ から読み終えたときに状態 $q$ にいるものの個数を $N_{k} (q)$ とおく。

手順 1: 初期値。 長さ $0$ の文字列は空文字列 1 個だけで、読み終えた状態は $q_{0}$ なので
$N_{0} (q_{0}) = 1, N_{0} (q_{1}) = 0, N_{0} (q_{2}) = 0.$

手順 2: 漸化式を立てる。 長さ $k + 1$ の文字列は、長さ $k$ の文字列の後ろに 1 文字 $c$ を付けたものである。 $N_{k + 1} (q^{'}) = \sum_{δ (q, c) = q^{'}} N_{k} (q)$ に従い、遷移表で「行き先が $q^{'}$ になる矢印」をすべて集める。
- $q_{0}$ に入る矢印: $δ (q_{0}, 0) = q_{0}$ , $δ (q_{1}, 0) = q_{0}$
- $q_{1}$ に入る矢印: $δ (q_{0}, 1) = q_{1}$
- $q_{2}$ に入る矢印: $δ (q_{1}, 1) = q_{2}$ , $δ (q_{2}, 0) = q_{2}$ , $δ (q_{2}, 1) = q_{2}$

よって
$N_{k + 1} (q_{0}) = N_{k} (q_{0}) + N_{k} (q_{1}),$
$N_{k + 1} (q_{1}) = N_{k} (q_{0}),$
$N_{k + 1} (q_{2}) = N_{k} (q_{1}) + 2 N_{k} (q_{2}) .$

手順 3: 順に計算する。 $(N_{k} (q_{0}), N_{k} (q_{1}), N_{k} (q_{2}))$ を並べると

$k$	$N_{k} (q_{0})$	$N_{k} (q_{1})$	$N_{k} (q_{2})$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	2	3	8
4	5	3	8	16
5	8	5	19	32
6	13	8	43	64
7	21	13	94	128
8	34	21	201	256

例えば $k = 3$ から $k = 4$ では $N_{4} (q_{0}) = 3 + 2 = 5$ , $N_{4} (q_{1}) = 3$ , $N_{4} (q_{2}) = 2 + 2 \cdot 3 = 8$ である。各行の合計が $2^{k}$ になっていることで計算を確かめられる。

手順 4: 受理状態の個数を足す。 受理状態は $q_{0}, q_{1}$ なので、求める個数は
$N_{8} (q_{0}) + N_{8} (q_{1}) = 34 + 21 = 55.$

（参考: この $M$ は「 $1$ が 2 つ続く部分を含まない文字列」を受理する。）

答え: $55$

別解

状態 $q_{2}$ は入力に関わらず $q_{2}$ に留まり、受理状態ではない（行き止まりの状態）。したがって $M$ に受理される文字列は、 $q_{2}$ に一度も到達しない文字列である。

$q_{2}$ に入る遷移は $q_{1} 1 q_{2}$ だけである。 $q_{1}$ にいるのは「直前の文字が 1 で、それまでに $q_{2}$ に入っていない」ときに限られる（ $q_{0}$ は初期状態か、直前が 0 の状態）。よって $q_{2}$ に到達することは、文字列に連続した部分列 $11$ が現れることと同値である。

したがって、受理される文字列は「 $11$ を含まない 0,1 列」である。

長さ $n$ の $11$ を含まない文字列の個数を $a_{n}$ とする。末尾が 0 なら前の $n - 1$ 文字は自由に $11$ を含まない列で $a_{n - 1}$ 通り。末尾が 1 なら直前は 0 でなければならず、その前の $n - 2$ 文字が $a_{n - 2}$ 通り。よって $a_{n} = a_{n - 1} + a_{n - 2}$ であり、 $a_{1} = 2, a_{2} = 3$ である。

$a_{3} = 5, a_{4} = 8, a_{5} = 13, a_{6} = 21, a_{7} = 34, a_{8} = 55$ 。

検算：状態 $q_{0}, q_{1}$ にいる文字列の数を $x_{n}, y_{n}$ とする。漸化式は $x_{n + 1} = x_{n} + y_{n}$ 、 $y_{n + 1} = x_{n}$ である。初期値は $(x_{0}, y_{0}) = (1, 0)$ 。これを繰り返すと $(1, 0) \to (1, 1) \to (2, 1) \to (3, 2) \to (5, 3) \to (8, 5) \to (13, 8) \to (21, 13) \to (34, 21)$ となり、 $n = 8$ で $x_{8} + y_{8} = 34 + 21 = 55$ となって一致する。

状態	入力 $0$	入力 $1$
$A$	$B$	$A$
$B$	$C$	$A$
$C$	$C$	$B$

状態 \\ 入力	$a$	$b$
$p$	$q$	$r$
$q$	$p$	$q$
$r$	$r$	$p$

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

状態	入力 $0$	入力 $1$	入力 $2$
$s$	$s$	$t$	$t$
$t$	$s$	$s$	$t$

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題

$k$	$N_{k} (q_{0})$	$N_{k} (q_{1})$	$N_{k} (q_{2})$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	2	3	8
4	5	3	8	16
5	8	5	19	32
6	13	8	43	64
7	21	13	94	128
8	34	21	201	256

$k$	$N_{k} (q_{0})$	$N_{k} (q_{1})$	$N_{k} (q_{2})$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	2	3	8
4	5	3	8	16
5	8	5	19	32
6	13	8	43	64
7	21	13	94	128
8	34	21	201	256

$k$	$N_{k} (q_{0})$	$N_{k} (q_{1})$	$N_{k} (q_{2})$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	2	3	8
4	5	3	8	16
5	8	5	19	32
6	13	8	43	64
7	21	13	94	128
8	34	21	201	256