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

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

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

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

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

$M$ が受理する長さ $6$ の文字列（ $Σ$ 上の文字列）の個数を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「状態ごとの文字列数の漸化式」を使う。長さ $k$ の文字列を読んだ後に各状態にいる文字列の個数 $N_{k} (q_{0}), N_{k} (q_{1}), N_{k} (q_{2})$ を、 $k = 0$ から順に更新していこう。

ヒント 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} (q_{2})$ , $N_{k + 1} (q_{2}) = N_{k} (q_{1}) + N_{k} (q_{2})$ となる。初期値は $(1, 0, 0)$ 。

ヒント 3

計算を進めると $k = 3$ で $(3, 3, 2)$ 、 $k = 4$ で $(6, 5, 5)$ 、 $k = 5$ で $(11, 11, 10)$ になる。あと 1 段更新して、受理状態の分を足そう。

答えと解説

答えを見る

42

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

解説を読む

長さ $k$ の文字列 $w$ のうち、初期状態 $q_{0}$ から読んで最後の状態 $δ^(q_{0}, w)$ が $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$ 文字を付け加えたものである。状態 $q^{'}$ に入る矢印（ $δ (q, c) = q^{'}$ となる組 $(q, c)$ ）を表から探すと
- $q_{0}$ に入るのは $δ (q_{0}, 0) = q_{0}$ , $δ (q_{1}, 1) = q_{0}$
- $q_{1}$ に入るのは $δ (q_{0}, 1) = q_{1}$ , $δ (q_{2}, 0) = q_{1}$
- $q_{2}$ に入るのは $δ (q_{1}, 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} (q_{2}),$
$N_{k + 1} (q_{2}) = N_{k} (q_{1}) + N_{k} (q_{2}) .$

手順 3：順に計算する
$(N_{k} (q_{0}), N_{k} (q_{1}), N_{k} (q_{2}))$ を並べると
- $k = 0$ : $(1, 0, 0)$
- $k = 1$ : $(1 + 0, 1 + 0, 0 + 0) = (1, 1, 0)$
- $k = 2$ : $(1 + 1, 1 + 0, 1 + 0) = (2, 1, 1)$
- $k = 3$ : $(2 + 1, 2 + 1, 1 + 1) = (3, 3, 2)$
- $k = 4$ : $(3 + 3, 3 + 2, 3 + 2) = (6, 5, 5)$
- $k = 5$ : $(6 + 5, 6 + 5, 5 + 5) = (11, 11, 10)$
- $k = 6$ : $(11 + 11, 11 + 10, 11 + 10) = (22, 21, 21)$

（検算：各段の和は $1, 2, 4, 8, 16, 32, 64$ で、長さ $k$ の文字列全体の個数 $2^{k}$ に一致する。）

手順 4：受理状態について足す
受理状態は $q_{1}, q_{2}$ なので、求める個数は
$N_{6} (q_{1}) + N_{6} (q_{2}) = 21 + 21 = 42.$

別解

長さ $n$ の文字列を読んだ後に状態 $q_{0}, q_{1}, q_{2}$ にいる文字列の個数を $(a_{n}, b_{n}, c_{n})$ とする。

遷移表から、次の漸化式が得られる。
- $q_{0}$ に入る遷移は、 $q_{0}$ から入力 $0$ と $q_{1}$ から入力 $1$ なので、 $a_{n + 1} = a_{n} + b_{n}$
- $q_{1}$ に入る遷移は、 $q_{0}$ から入力 $1$ と $q_{2}$ から入力 $0$ なので、 $b_{n + 1} = a_{n} + c_{n}$
- $q_{2}$ に入る遷移は、 $q_{1}$ から入力 $0$ と $q_{2}$ から入力 $1$ なので、 $c_{n + 1} = b_{n} + c_{n}$

初期値は $(a_{0}, b_{0}, c_{0}) = (1, 0, 0)$ である。順に計算する。
- $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$ で合計が $2^{n}$ になっている。 $n = 6$ では $22 + 21 + 21 = 64 = 2^{6}$ である。

受理状態は $q_{1}$ と $q_{2}$ なので、受理される長さ $6$ の文字列の個数は $b_{6} + c_{6} = 21 + 21 = 42$ 。

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

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

状態	入力 $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$

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

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題