遷移行列による受理文字列数の一般項

DFA の遷移を数える行列 $A$ （ $A_{q q^{'}}$ は $q$ から $q^{'}$ へ移る記号の個数）を作り、 $A$ の固有値・対角化を使って、受理される長さ $n$ の文字列の個数 $e_{q_{0}}^{T} A^{n} 1_{F}$ を $n$ の式で表せる

前提

状態ごとの文字列数の漸化式（大学数学オートマトン・形式言語）
対角化と行列の累乗（大学数学線形代数）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
状態ごとの文字列数の漸化式（大学数学オートマトン・形式言語）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
順列・円順列・重複順列（数学A 場合の数と確率）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）
掃き出し法による逆行列（大学数学線形代数）
基底の変換と表現行列（大学数学線形代数）
対角化と行列の累乗（大学数学線形代数）

説明

DFA の状態どうしの移り方を、記号の個数を成分とする行列 $A$ にまとめます。こうすると、受理される長さ $n$ の文字列の個数を、 $n = 10$ のような具体的な値ごとではなく、 $n$ の式（一般項）として求められます。行列 $A$ を対角化して $A^{n}$ を $n$ の式で表すのが中心の作業です。言語の大きさの増え方を調べるときや、条件付きの文字列を数える組合せの問題で使います。

なぜそうしてよいのか

状態を $q_{1}, \dots, q_{m}$ と番号付けし、 $A_{q q^{'}}$ を「 $δ (q, c) = q^{'}$ となる記号 $c$ の個数」とします。長さ $k$ の文字列を読んで各状態に到達する個数を並べた行ベクトルを $N_{k}^{T} = (N_{k} (q_{1}), \dots, N_{k} (q_{m}))$ とおきます。前提の漸化式 $N_{k + 1} (q^{'}) = \sum_{δ (q, c) = q^{'}} N_{k} (q)$ では、右辺で $N_{k} (q)$ がちょうど $A_{q q^{'}}$ 回足されます。したがって $N_{k + 1} (q^{'}) = \sum_{q} N_{k} (q) A_{q q^{'}}$ となり、行列で書くと $N_{k + 1}^{T} = N_{k}^{T} A$ です。

長さ $0$ の文字列は空文字列だけで、初期状態 $q_{0}$ にとどまります。よって $N_{0}^{T} = e_{q_{0}}^{T}$ （ $q_{0}$ の成分だけ $1$ 、他は $0$ ）で、これを繰り返すと $N_{n}^{T} = e_{q_{0}}^{T} A^{n}$ になります。受理される文字列の個数は、受理状態の集合 $F$ に属する状態の成分の和です。 $F$ の状態の成分を $1$ 、それ以外を $0$ とした列ベクトルを $1_{F}$ とすると、求める個数は $e_{q_{0}}^{T} A^{n} 1_{F}$ です。同じことを別の見方で言うと、 $(A^{n})_{q q^{'}}$ は「 $q$ から $n$ 文字で $q^{'}$ に着く文字列の個数」です。1 文字ずつの選び方を積の法則で掛け、途中で通る状態について和の法則で足したものが、行列の積の定義そのものになっています。

あとは $A^{n}$ を $n$ の式で書ければ終わりです。 $A$ が対角化できて $A = P D P^{- 1}$ （ $D = diag (λ_{1}, \dots, λ_{m})$ ）となれば、 $A^{n} = P D^{n} P^{- 1}$ で $D^{n} = diag (λ_{1}^{n}, \dots, λ_{m}^{n})$ です。そのため答えは、 $n$ によらない定数 $c_{i}$ を使って $\sum_{i} c_{i} λ_{i}^{n}$ の形になります。なお、 $A$ が対角化できない場合はこの方法をそのままでは使えません。

手順

状態に順番を付け、各状態の組 $(q, q^{'})$ について $q$ から $q^{'}$ へ移る記号の個数を数え、行列 $A$ （ $A_{q q^{'}}$ がその個数）を作る。各行の和は記号の個数 $∣Σ∣$ になるので、これで検算する。
初期状態を表す $e_{q_{0}}$ と受理状態を表す $1_{F}$ を作り、求める個数を $a_{n} = e_{q_{0}}^{T} A^{n} 1_{F}$ と書く。
特性方程式 $det (λ I - A) = 0$ を解いて固有値を求め、固有ベクトルを並べて $P$ と $D$ を作る。このとき対角化できること（一次独立な固有ベクトルが状態の個数だけそろうこと）を確かめる。
$A^{n} = P D^{n} P^{- 1}$ を計算し、 $e_{q_{0}}^{T} P D^{n} P^{- 1} 1_{F}$ を整理して $\sum_{i} c_{i} λ_{i}^{n}$ の形にする。
$n = 0, 1, 2$ を代入し、直接数えた値（または前提の漸化式で求めた値）と一致するか確かめる。

例題

アルファベット $Σ = {a, b, c}$ 上の DFA を考える。状態は $q_{0}, q_{1}$ の 2 つで、初期状態は $q_{0}$ 、受理状態は $q_{0}$ だけである。遷移は次の表のとおり。

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

この DFA が受理する長さ $n$ （ $n$ は 0 以上の整数）の文字列の個数 $a_{n}$ を $n$ の式で求めよ。

例題の解答

手順 1（行列を作る）
状態の順番を $q_{0}, q_{1}$ とします。 $q_{0}$ からは $a$ の 1 個で $q_{0}$ へ、 $b, c$ の 2 個で $q_{1}$ へ移ります。 $q_{1}$ からは $b, c$ の 2 個で $q_{0}$ へ、 $a$ の 1 個で $q_{1}$ へ移ります。よって
$A = (1221)$
です。各行の和は $3 = ∣Σ∣$ となり、検算も合います。

手順 2（求める量を式にする）
$e_{q_{0}} = (10)$ 、 $1_{F} = (10)$ なので、 $a_{n} = e_{q_{0}}^{T} A^{n} 1_{F} = (A^{n})_{q_{0} q_{0}}$ です。

手順 3（対角化する）
特性多項式は $det (λ I - A) = (λ - 1)^{2} - 4 = (λ - 3) (λ + 1)$ なので、固有値は $3, - 1$ です。 $λ = 3$ の固有ベクトルとして $(11)$ 、 $λ = - 1$ の固有ベクトルとして $(1 - 1)$ がとれます。固有値が異なるので、この 2 つは一次独立で、 $A$ は対角化できます。
$P = (11 1 - 1), D = (30 0 - 1), P^{- 1} = \frac{1}{2} (11 1 - 1)$

手順 4（ $A^{n}$ を計算する）
$P D^{n} = (3^{n} 3^{n} (- 1)^{n} - (- 1)^{n})$
なので、
$A^{n} = P D^{n} P^{- 1} = \frac{1}{2} (3^{n} + (- 1)^{n} 3^{n} - (- 1)^{n} 3^{n} - (- 1)^{n} 3^{n} + (- 1)^{n})$
となります。よって $a_{n} = \frac{3 ^{n} + ( - 1 ) ^{n}}{2}$ です。

手順 5（小さい $n$ で確かめる）
- $n = 0$ ：式の値は $\frac{1 + 1}{2} = 1$ 。空文字列だけが受理されるので一致します。
- $n = 1$ ：式の値は $\frac{3 - 1}{2} = 1$ 。受理されるのは $a$ だけなので一致します。
- $n = 2$ ：式の値は $\frac{9 + 1}{2} = 5$ 。受理されるのは $aa, bb, b c, c b, cc$ の 5 個なので一致します。

なお、この DFA は「 $b$ と $c$ の個数の合計が偶数である文字列」を受理するものです。

答え: $\frac{3 ^{n} + ( - 1 ) ^{n}}{2}$

よくある誤り

同じ移り先へ行く記号が複数あるのに、成分を $1$ としてしまう誤り。正しくは記号の個数を入れる。例題なら $A_{q_{0} q_{1}} = 2$ （ $b$ と $c$ の 2 個）で、 $1$ ではない。
添字の向きを逆にして $A^{T}$ を使い、 $e_{q_{0}}^{T} (A^{T})^{n} 1_{F}$ を計算してしまう誤り。これは $1_{F}^{T} A^{n} e_{q_{0}}$ と同じで、「受理状態から出発して $q_{0}$ に着く文字列の個数」になってしまう。正しくは $A_{q q^{'}}$ を「 $q$ から $q^{'}$ へ」とし、 $e_{q_{0}}^{T} A^{n} 1_{F}$ を計算する。
$A^{n} = P^{- 1} D^{n} P$ と順番を取り違える誤り。 $A = P D P^{- 1}$ （ $P$ の列が固有ベクトル）のときは、正しくは $A^{n} = P D^{n} P^{- 1}$ である。
固有値に $0$ があるとき、一般項 $\sum c_{i} λ_{i}^{n}$ の $0^{n}$ の項を何も考えずに $0$ として、 $n = 0$ でも同じ式が成り立つとしてしまう誤り。 $D^{0} = I$ なので $n = 0$ では $0^{0} = 1$ として扱う必要がある。式を $n \geq 1$ に限って書くなど、適用できる範囲を明記する。

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

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

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

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

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

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

遷移行列による受理文字列数の一般項

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題