正規言語に属する長さ n の文字列の数え上げ

$(a + ab + abb)^{*}$ のような正規表現の言語に属する文字列をブロックへの分解（またはオートマトンへの変換）で漸化式に直し、 $b$ の個数の偶奇などの条件も状態に加えて、長さ $n$ の文字列の個数を求められる

前提

正規表現が表す言語と文字列の判定（大学数学オートマトン・形式言語）
状態ごとの文字列数の漸化式（大学数学オートマトン・形式言語）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

正規表現が表す言語と文字列の判定（大学数学オートマトン・形式言語）
決定性有限オートマトンの動作と受理判定（大学数学オートマトン・形式言語）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
状態ごとの文字列数の漸化式（大学数学オートマトン・形式言語）

説明

正規表現で表された言語について、長さ $n$ の文字列がいくつあるかを数える方法を学びます。文字列を決まった形のブロックに切り分けて「最後のブロックが何か」で場合分けすると、個数の漸化式が得られます。さらに「 $b$ の個数が偶数」のような条件は、偶数・奇数の 2 つの状態に分けて数えれば同じ方法で扱えます。符号の数え上げや、パターンを避ける文字列の個数などでよく使います。

なぜそうしてよいのか

例として $L = L ((a + ab + abb)^{*})$ を考えます。この言語の文字列は、ブロック $a, ab, abb$ を何個か（0 個でもよい）つないだものです。どのブロックも $a$ で始まり、 $a$ はブロックの先頭にしか現れません。そのため、 $L$ の文字列は「各 $a$ の直前で切る」以外の切り方ができず、ブロックへの分け方はただ 1 通りに決まります。分け方が 1 通りなので、「文字列を 1 つ数える」ことと「ブロックの並びを 1 つ数える」ことが同じになります。

長さ $n$ の文字列の個数を $f (n)$ とします。 $n \geq 1$ のとき、最後のブロックは $a$ （長さ 1）、 $ab$ （長さ 2）、 $abb$ （長さ 3）のどれかで、この 3 つの場合は重なりません。最後のブロックを取り除いた残りは、長さ $n - 1, n - 2, n - 3$ の $L$ の文字列で、どれでもよいです。和の法則から $f (n) = f (n - 1) + f (n - 2) + f (n - 3)$ となります。ただし $f (0) = 1$ （空文字列 1 個）、負の長さについては $f (\cdot) = 0$ とします。これは、ブロックの区切り目を状態とする DFA で、前提の技能の更新式 $N_{k + 1} (q^{'}) = \sum_{δ (q, c) = q^{'}} N_{k} (q)$ を使うことを、ブロック単位にまとめて行っているのと同じです。

「 $b$ の個数が偶数」という条件を加えるときは、 $b$ が偶数個の文字列の個数 $E_{n}$ と奇数個の個数 $O_{n}$ を別々に数えます。最後のブロックを付け足すと、そのブロックに含まれる $b$ の個数の偶奇だけ偶奇が変わります。 $a$ は $b$ を 0 個含むので偶奇は変わりません。 $ab$ は 1 個含むので偶奇が反転します。 $abb$ は 2 個含むので偶奇は変わりません。これは DFA に「偶奇」という状態を付け加えて、状態ごとに数えることにあたります。

手順

文字列がブロックに一通りに分解できることを確かめる。一通りにならないときや分解が難しいときは、言語を受理する DFA を作り、状態ごとの漸化式に切り替える。
長さ $n$ の個数を $f (n)$ とおき、最後のブロックで場合分けする。ブロックの長さが $ℓ_{1}, \dots, ℓ_{m}$ のとき $f (n) = \sum_{i} f (n - ℓ_{i})$ とする。初期値は $f (0) = 1$ 、負の長さでは $0$ とする。
偶奇などの追加条件があるときは、状態ごとの個数（例: $E_{n}, O_{n}$ ）に分ける。各ブロックがどの状態をどの状態に移すかを調べて、状態ごとの漸化式を立てる。
$n = 0$ から順に表で計算し、条件を満たす状態の値を答えにする。検算として、全状態の和が条件なしの $f (n)$ に一致するかを確かめる。

例題

アルファベット ${a, b}$ 上の正規表現 $(a + ab + abb)^{*}$ の言語に属する長さ $6$ の文字列のうち、 $b$ の個数が偶数であるものの個数を求めよ。

例題の解答

手順1: どのブロック $a, ab, abb$ も $a$ で始まり、 $a$ は先頭にしか現れません。したがって各 $a$ の直前で切る分け方しかなく、分解は一通りに決まります。

手順2: 長さ $n$ の文字列の総数 $f (n)$ は $f (n) = f (n - 1) + f (n - 2) + f (n - 3)$ 、 $f (0) = 1$ を満たします（検算に使います）。

手順3: $b$ が偶数個のものの個数を $E_{n}$ 、奇数個のものの個数を $O_{n}$ とします。 $a$ と $abb$ は偶奇を変えず、 $ab$ は偶奇を反転させます。よって
$E_{n} = E_{n - 1} + O_{n - 2} + E_{n - 3}, O_{n} = O_{n - 1} + E_{n - 2} + O_{n - 3}$
です。初期値は $E_{0} = 1, O_{0} = 0$ （空文字列は $b$ が 0 個）、負の添字の値は $0$ とします。

手順4: 順に計算します。
- $n = 1$ : $E_{1} = 1, O_{1} = 0$
- $n = 2$ : $E_{2} = 1 + 0 = 1, O_{2} = 0 + 1 = 1$ （ $aa$ と $ab$ に対応）
- $n = 3$ : $E_{3} = 1 + 0 + 1 = 2, O_{3} = 1 + 1 + 0 = 2$
- $n = 4$ : $E_{4} = 2 + 1 + 1 = 4, O_{4} = 2 + 1 + 0 = 3$
- $n = 5$ : $E_{5} = 4 + 2 + 1 = 7, O_{5} = 3 + 2 + 1 = 6$
- $n = 6$ : $E_{6} = 7 + 3 + 2 = 12, O_{6} = 6 + 4 + 2 = 12$

検算: $f (n)$ は $1, 1, 2, 4, 7, 13, 24$ と進みます。各 $n$ で $E_{n} + O_{n} = f (n)$ が成り立ち、 $n = 6$ では $12 + 12 = 24$ です。

よって求める個数は $12$ です。

答え: $12$

よくある誤り

分解が一通りでないのに、ブロックの並べ方を数えてしまう誤り。例えば $(a + b + ab)^{*}$ で $f (n) = 2 f (n - 1) + f (n - 2)$ とすると、 $f (2) = 5$ になります。正しくは $ab$ が $a \cdot b$ とも分けられるので、言語は ${a, b}$ 上のすべての文字列で、 $f (n) = 2^{n}$ （ $f (2) = 4$ ）です。分解が一通りでないときは DFA を作って数えます。
初期値を $f (0) = 0$ としてしまう誤り。正しくは、空文字列は $(\dots)^{*}$ に属するので $f (0) = 1$ です。 $f (0) = 0$ にすると、 $f (1) = f (0) = 0$ のように全部が 0 になってしまいます。
ブロックが偶奇に与える影響を取り違える誤り。例えば $abb$ で偶奇が反転するとして $E_{n} = E_{n - 1} + O_{n - 2} + O_{n - 3}$ とするのは誤りです。正しくは、 $abb$ は $b$ を 2 個含むので偶奇は変わらず、 $E_{n} = E_{n - 1} + O_{n - 2} + E_{n - 3}$ です。
追加条件の状態の更新で、移る前と後の状態を逆にしてしまう誤り。 $ab$ を付けて偶数になるのは、付ける前が奇数のものなので、正しくは $E_{n}$ の式に $O_{n - 2}$ が入ります（ $E_{n - 2}$ ではありません）。

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

入口の問題

この技能を使う問題

難易度 4（大学院入試の標準レベル）
アルファベット $Σ = {a, b}$ 上の正規表現
$r = (a + ab + abb)^{*}$
を考え、 $r$ が表す言語を $L (r)$ とする（ $+$ は和集合、 $^{*}$ はクリーネ閉包を表す）。
長さ $8$ の文字列 $w \in Σ^{*}$ のうち、次の 2 つの条件をともに満たすものの個数を求めよ。
- $w \in L (r)$
- $w$ に含まれる $b$ の個数が偶数である（ $0$ 個も偶数とみなす）