状態ごとの文字列数の漸化式

DFA の各状態に到達する長さ $k$ の文字列の個数を $N_{k + 1} (q^{'}) = \sum_{δ (q, c) = q^{'}} N_{k} (q)$ で順に更新し、受理される長さ $n$ （ $n = 10$ など具体的な値）の文字列の個数を求められる

前提

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
和の法則・積の法則と樹形図（数学A 場合の数と確率）

この技能までの道筋（4 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）

説明

DFA（決定性有限オートマトン）が受理する長さ $n$ の文字列が何個あるかを、文字列を 1 つずつ書き出さずに数える技能です。長さ $k$ の文字列を「読み終えたときにどの状態にいるか」で分類し、状態ごとの個数 $N_{k} (q)$ を $k = 0, 1, 2, \dots$ と順に更新していきます。「連続する 1 を含まない」「1 の個数が 3 の倍数」のような条件をみたす文字列の個数を求める場面で使います。 $2^{10}$ 通りを全部調べる代わりに、状態の数 × $n$ 回ほどの足し算で答えが出ます。

なぜそうしてよいのか

DFA は決定的です。そのため、どの文字列 $w$ にも、読み終えた状態 $δ^(q_{0}, w)$ がただ 1 つ決まります。そこで、長さ $k$ の文字列のうち $δ^(q_{0}, w) = q$ となるものの個数を $N_{k} (q)$ と書きます。長さ $k$ の文字列はどれも、ちょうど 1 つの状態に振り分けられます。つまり状態ごとのグループは互いに重ならず、しかも全体をもれなく分けています。

長さ $k + 1$ の文字列は、長さ $k$ の文字列 $w$ の後ろに 1 文字 $c$ を付けた形 $w c$ に、ただ 1 通りに書けます。その最後の状態は $δ^(q_{0}, w c) = δ (δ^(q_{0}, w), c)$ です。したがって $w c$ が状態 $q^{'}$ で終わるのは、「 $w$ が状態 $q$ で終わり、かつ $δ (q, c) = q^{'}$ 」となるときに限ります。組 $(q, c)$ を 1 つ決めると、そのような $w c$ は $w$ の選び方の数だけ、つまり $N_{k} (q)$ 個あります。組 $(q, c)$ が違えば、できる文字列も違います。よって和の法則から
$N_{k + 1} (q^{'}) = δ (q, c) = q^{'} \sum N_{k} (q)$
が成り立ちます。右辺の和は、 $q^{'}$ に入ってくる遷移（状態と文字の組）すべてについてとります。

出発点は長さ 0 の空文字列 $ε$ だけで、これは初期状態 $q_{0}$ にいます。ですから $N_{0} (q_{0}) = 1$ で、それ以外の状態では $N_{0} (q) = 0$ です。 $n$ 回更新したあと、受理状態の集合 $F$ についての和 $\sum_{q \in F} N_{n} (q)$ が、受理される長さ $n$ の文字列の個数になります。

手順

初期値を置く: 初期状態だけ $N_{0} (q_{0}) = 1$ とし、他の状態はすべて $N_{0} (q) = 0$ とする。
遷移表を「行き先ごと」に読み替える: 各状態 $q^{'}$ について、 $δ (q, c) = q^{'}$ となる組 $(q, c)$ をすべて書き出す。同じ $q$ から 2 つの文字で $q^{'}$ に行くなら、 $N_{k} (q)$ を 2 回足す。
更新式 $N_{k + 1} (q^{'}) = \sum_{δ (q, c) = q^{'}} N_{k} (q)$ を使い、 $k = 0, 1, \dots, n - 1$ の順に表を埋める。
検算する: 全状態・全文字について遷移が定義されている DFA なら、各 $k$ で全状態の和は (文字の種類数) $^{k}$ になる。これを確かめる。
受理状態についての和 $\sum_{q \in F} N_{n} (q)$ を計算し、答えとする。

例題

アルファベット ${0, 1}$ 上の DFA を次の表で定める。状態は $A, B, D$ 、初期状態は $A$ 、受理状態は $A$ と $B$ である。

状態	0 を読む	1 を読む
$A$	$A$	$B$
$B$	$A$	$D$
$D$	$D$	$D$

この DFA が受理する長さ $8$ の文字列の個数を求めよ。

例題の解答

手順1（初期値）: $N_{0} (A) = 1, N_{0} (B) = 0, N_{0} (D) = 0$ とする。

手順2（行き先ごとの読み替え）: 各状態に入ってくる遷移は次のとおりである。
- $A$ に入る遷移: $(A, 0), (B, 0)$
- $B$ に入る遷移: $(A, 1)$
- $D$ に入る遷移: $(B, 1), (D, 0), (D, 1)$

よって更新式は
$N_{k + 1} (A) = N_{k} (A) + N_{k} (B), N_{k + 1} (B) = N_{k} (A), N_{k + 1} (D) = N_{k} (B) + 2 N_{k} (D)$
となる。

手順3（表を埋める）: $(N_{k} (A), N_{k} (B), N_{k} (D))$ は順に次のようになる。
- $k = 0$ : $(1, 0, 0)$
- $k = 1$ : $(1, 1, 0)$
- $k = 2$ : $(2, 1, 1)$
- $k = 3$ : $(3, 2, 3)$
- $k = 4$ : $(5, 3, 8)$
- $k = 5$ : $(8, 5, 19)$
- $k = 6$ : $(13, 8, 43)$
- $k = 7$ : $(21, 13, 94)$
- $k = 8$ : $(34, 21, 201)$

手順4（検算）: この DFA は全状態・全文字について遷移が定義されている。各段の和は $1, 2, 4, 8, 16, 32, 64, 128, 256$ で、確かに $2^{k}$ になっている。例えば $k = 8$ では $34 + 21 + 201 = 256 = 2^{8}$ である。

手順5（受理状態の和）: $N_{8} (A) + N_{8} (B) = 34 + 21 = 55$ 。

なお、この DFA が受理するのは「 $11$ を部分文字列として含まない（連続する $11$ を含まない）文字列」である。

答え: $55$

よくある誤り

初期値をすべての状態で $N_{0} (q) = 1$ としたり、長さ 1 から始めて $N_{1} (q_{0}) = 1$ としたりしてしまう誤り。正しくは、初期状態にいるのは空文字列だけなので、 $N_{0} (q_{0}) = 1$ とし、他はすべて $0$ とする。
入ってくる遷移ではなく、出ていく遷移で式を作ってしまう誤り。例えば例題の表の $B$ の行を見て、行き先が $A, D$ だからと $N_{k + 1} (B) = N_{k} (A) + N_{k} (D)$ としたり、 $D$ の行から $N_{k + 1} (D) = 2 N_{k} (D)$ としたりしてしまう。正しくは、 $δ (q, c) = q^{'}$ となる組 $(q, c)$ 、つまり $q^{'}$ に入ってくる遷移の元の状態の値を足す。 $B$ に入る遷移は $(A, 1)$ だけなので $N_{k + 1} (B) = N_{k} (A)$ である。 $A$ に入る遷移は $(A, 0), (B, 0)$ なので $N_{k + 1} (A) = N_{k} (A) + N_{k} (B)$ である。
同じ状態から 2 つの文字で同じ行き先に行く遷移を、1 回しか数えない誤り。例の $D$ では $δ (D, 0) = δ (D, 1) = D$ である。したがって $N_{k + 1} (D) = N_{k} (B) + N_{k} (D)$ ではなく、正しくは $N_{k + 1} (D) = N_{k} (B) + 2 N_{k} (D)$ である。
最後に全状態の和をとったり、受理状態でない状態まで足したりしてしまう誤り。例で $34 + 21 + 201 = 256$ と答えるのは誤りで、正しくは受理状態 $A, B$ だけを足して $34 + 21 = 55$ とする。また、更新を $n - 1$ 回で止めたり $n + 1$ 回行ったりしないよう、添字 $k$ が文字列の長さと一致していることを確かめる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

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

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

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

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

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

状態	$a$	$b$	$c$
$p$	$q$	$s$	$p$
$q$	$r$	$p$	$q$
$r$	$s$	$q$	$r$
$s$	$p$	$r$	$s$

状態	$0$	$1$	$2$
$s_{0}$	$s_{1}$	$s_{1}$	$s_{2}$
$s_{1}$	$s_{1}$	$s_{0}$	$s_{2}$
$s_{2}$	$s_{0}$	$s_{0}$	$s_{2}$

状態	$a$	$b$	$c$
$p$	$p$	$q$	$r$
$q$	$p$	$p$	$r$
$r$	$q$	$r$	$r$

この技能の次に学べること

遷移行列による受理文字列数の一般項（大学数学オートマトン・形式言語）
正規言語に属する長さ n の文字列の数え上げ（大学数学オートマトン・形式言語）