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

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

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

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

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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

技能「状態ごとの文字列数の漸化式」を使う。長さ $k$ の文字列で状態 $q$ に着くものの個数 $N_{k} (q)$ を、 $k = 0$ から 1 文字ずつ増やして更新していこう。

ヒント 2

遷移表から各状態に入ってくる遷移を集めると、 $N_{k + 1} (A) = N_{k} (A) + N_{k} (B)$ , $N_{k + 1} (B) = N_{k} (A) + N_{k} (C)$ , $N_{k + 1} (C) = N_{k} (B) + N_{k} (C)$ となる。初期値は $N_{0} (A) = 1, N_{0} (B) = N_{0} (C) = 0$ 。

ヒント 3

順に計算すると $(N_{k} (A), N_{k} (B), N_{k} (C))$ は $k = 4$ で $(6, 5, 5)$ 、 $k = 5$ で $(11, 11, 10)$ 、 $k = 6$ で $(22, 21, 21)$ 、 $k = 7$ で $(43, 43, 42)$ となる。あと 1 回更新して $N_{8} (C)$ を求めよう。

答えと解説

答えを見る

85

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

解説を読む

方針長さ $k$ の文字列のうち、初期状態 $A$ から読み始めて状態 $q$ で止まるものの個数を $N_{k} (q)$ とおく。DFA なので、どの文字列も止まる状態はちょうど 1 つに決まる。長さ $k + 1$ の文字列で状態 $q^{'}$ に着くものは、「長さ $k$ で状態 $q$ に着き、最後の 1 文字 $c$ で $δ (q, c) = q^{'}$ と移る」ものに一通りに分けられるから、和の法則により
$N_{k + 1} (q^{'}) = δ (q, c) = q^{'} \sum N_{k} (q)$
が成り立つ。

漸化式を作る 遷移表から、各状態へ入ってくる矢印を集める。
- $A$ に入る遷移: $δ (A, 1) = A$ , $δ (B, 1) = A$
- $B$ に入る遷移: $δ (A, 0) = B$ , $δ (C, 1) = B$
- $C$ に入る遷移: $δ (B, 0) = C$ , $δ (C, 0) = C$

したがって
$N_{k + 1} (A) = N_{k} (A) + N_{k} (B), N_{k + 1} (B) = N_{k} (A) + N_{k} (C), N_{k + 1} (C) = N_{k} (B) + N_{k} (C) .$

初期値 長さ $0$ の文字列は空列だけで、状態 $A$ にいるから $N_{0} (A) = 1, N_{0} (B) = 0, N_{0} (C) = 0$ 。

順に計算する

$k$	$N_{k} (A)$	$N_{k} (B)$	$N_{k} (C)$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	3	2	8
4	6	5	5	16
5	11	11	10	32
6	22	21	21	64
7	43	43	42	128
8	86	85	85	256

例えば $k = 7$ から $k = 8$ では $N_{8} (A) = 43 + 43 = 86$ , $N_{8} (B) = 43 + 42 = 85$ , $N_{8} (C) = 43 + 42 = 85$ である。各行の合計が $2^{k}$ になっていることで検算できる。

答え受理状態は $C$ のみなので、受理される長さ $8$ の文字列の個数は $N_{8} (C) = 85$ である。

別解

長さ $n$ の文字列を読んだ後に状態 $A, B, C$ にいる文字列の個数を $a_{n}, b_{n}, c_{n}$ とする。初期状態は $A$ なので $(a_{0}, b_{0}, c_{0}) = (1, 0, 0)$ 。

遷移表から次の漸化式が得られる。
- $A$ へ入る遷移は $A 1 A$ と $B 1 A$ なので $a_{n + 1} = a_{n} + b_{n}$ 。
- $B$ へ入る遷移は $A 0 B$ と $C 1 B$ なので $b_{n + 1} = a_{n} + c_{n}$ 。
- $C$ へ入る遷移は $B 0 C$ と $C 0 C$ なので $c_{n + 1} = b_{n} + c_{n}$ 。

これを順に計算する。
- $n = 1$ : $(1, 1, 0)$
- $n = 2$ : $(2, 1, 1)$
- $n = 3$ : $(3, 3, 2)$
- $n = 4$ : $(6, 5, 5)$
- $n = 5$ : $(11, 11, 10)$
- $n = 6$ : $(22, 21, 21)$
- $n = 7$ : $(43, 43, 42)$
- $n = 8$ : $(86, 85, 85)$

各 $n$ で和が $2^{n}$ になっている（ $n = 8$ では $86 + 85 + 85 = 256$ ）ので検算も合う。受理状態は $C$ のみなので、受理される文字列は $c_{8} = 85$ 個。

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

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

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

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

状態	$a$	$b$	$c$
$s$	$s$	$t$	$t$
$t$	$s$	$s$	$t$

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題

$k$	$N_{k} (A)$	$N_{k} (B)$	$N_{k} (C)$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	3	2	8
4	6	5	5	16
5	11	11	10	32
6	22	21	21	64
7	43	43	42	128
8	86	85	85	256

$k$	$N_{k} (A)$	$N_{k} (B)$	$N_{k} (C)$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	3	2	8
4	6	5	5	16
5	11	11	10	32
6	22	21	21	64
7	43	43	42	128
8	86	85	85	256

$k$	$N_{k} (A)$	$N_{k} (B)$	$N_{k} (C)$	合計
0	1	0	0	1
1	1	1	0	2
2	2	1	1	4
3	3	3	2	8
4	6	5	5	16
5	11	11	10	32
6	22	21	21	64
7	43	43	42	128
8	86	85	85	256