導出木の個数の数え上げ

CYK 法の表の各欄に「非終端記号 $X$ が $w_{i .. j}$ を生成する導出木の個数」を記録し、 $X \to Y Z$ と分割位置 $k$ について $\sum N_{Y} (i, k) N_{Z} (k + 1, j)$ を足し合わせて、 $w$ の導出木の個数を求められる

前提

CYK 法（大学数学オートマトン・形式言語）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

文脈自由文法の導出と導出木（大学数学オートマトン・形式言語）
CYK 法（大学数学オートマトン・形式言語）

説明

CYK 法では、表の各欄に「 $w_{i .. j}$ を生成できる非終端記号の集合」を書きました。ここでは各欄に数 $N_{X} (i, j)$ を書きます。これは「非終端記号 $X$ を根とし、 $w_{i .. j}$ を生成する導出木の個数」です。こうすると、文字列 $w$ の導出木の個数、つまり $w$ の構文解析の仕方が何通りあるかが求まります。文法があいまいかどうかを具体的な文字列で確かめたり、構文解析の候補を数えたりするときに使います。

なぜそうしてよいのか

文法はチョムスキー標準形とします。規則は $X \to Y Z$ （ $Y, Z$ は非終端記号）か $X \to a$ （ $a$ は終端記号）の形です。長さ $n \geq 1$ の文字列を $w = w_{1} w_{2} \dots w_{n}$ とし、 $w_{i .. j} = w_{i} \dots w_{j}$ と書きます。 $w_{i .. j}$ の長さは $j - i + 1$ です。長さ 1 の部分文字列 $w_{i .. i}$ を $X$ から生成する導出木は、規則 $X \to w_{i}$ を 1 回使う木しかありません。したがって、その規則があれば $N_{X} (i, i) = 1$ 、なければ $N_{X} (i, i) = 0$ です。

長さ 2 以上の $w_{i .. j}$ （ $i < j$ ）を $X$ から生成する導出木を 1 つ取ります。
- 根で使う規則は $X \to Y Z$ の形の 1 つに決まります。
- 左の部分木は $Y$ を根として $w_{i .. k}$ を、右の部分木は $Z$ を根として $w_{k + 1.. j}$ を生成します。よって分割位置 $k$ （ $i \leq k \leq j - 1$ ）も 1 つに決まります。

逆に、規則 $X \to Y Z$ と $k$ を固定すると、左の部分木は $N_{Y} (i, k)$ 通り、右の部分木は $N_{Z} (k + 1, j)$ 通りあります。両者は互いに無関係に選べるので、その組に対応する木は積 $N_{Y} (i, k) N_{Z} (k + 1, j)$ 個です（積の法則）。規則と $k$ の組が異なれば、根の規則か左右の境目が異なるので、木も異なります。そのため組ごとの個数をすべて足せば、重複なく数えられます（和の法則）。
$N_{X} (i, j) = X \to Y Z \sum k = i \sum j - 1 N_{Y} (i, k) N_{Z} (k + 1, j)$

右辺に現れるのは $w_{i .. k}$ と $w_{k + 1.. j}$ の値だけです。 $i \leq k \leq j - 1$ なので、どちらの長さも $1$ 以上 $j - i$ 以下です。つまり $w_{i .. j}$ （長さ $j - i + 1$ ）より短い部分文字列の値しか現れません。そのため CYK 法と同じく、短い部分文字列から順に埋めれば必ず計算できます。また、標準形には $X \to Y$ のような規則がありません。そのため導出木の大きさは文字列の長さで決まり、個数は有限になります。

手順

長さ 1 の欄を埋める：各 $i$ と各非終端記号 $X$ について、規則 $X \to w_{i}$ があれば $N_{X} (i, i) = 1$ 、なければ $0$ とする。
長さ $ℓ = 2, 3, \dots, n$ の順に、各区間 $(i, j)$ （ $j = i + ℓ - 1$ ）を処理する。
各 $X$ について、規則 $X \to Y Z$ と分割位置 $k = i, \dots, j - 1$ のすべての組を挙げ、各組の積 $N_{Y} (i, k) N_{Z} (k + 1, j)$ を求める。
それらの積をすべて足して $N_{X} (i, j)$ とする： $N_{X} (i, j) = \sum_{X \to Y Z} \sum_{k = i}^{j - 1} N_{Y} (i, k) N_{Z} (k + 1, j)$ 。
全体の欄の開始記号の値 $N_{S} (1, n)$ が $w$ の導出木の個数である。 $0$ なら $w$ は生成されない。

例題

開始記号を $S$ とする文法 $S \to S S ∣ a$ （チョムスキー標準形）について、文字列 $w = aaaa$ の導出木の個数を求めよ。

例題の解答

非終端記号は $S$ だけなので、 $N_{S} (i, j)$ を単に $N (i, j)$ と書きます。 $n = 4$ です。

【手順 1】規則 $S \to a$ があり、どの $w_{i}$ も $a$ です。よって $N (1, 1) = N (2, 2) = N (3, 3) = N (4, 4) = 1$ 。

【手順 2〜4】長さ 2 では、規則は $S \to S S$ だけで、分割位置は $k = i$ の 1 つだけです。
- $N (1, 2) = N (1, 1) N (2, 2) = 1$
- 同様に $N (2, 3) = 1$ 、 $N (3, 4) = 1$

長さ 3 では $k = i, i + 1$ の 2 通りがあります。
- $N (1, 3) = N (1, 1) N (2, 3) + N (1, 2) N (3, 3) = 1 \cdot 1 + 1 \cdot 1 = 2$
- $N (2, 4) = N (2, 2) N (3, 4) + N (2, 3) N (4, 4) = 1 + 1 = 2$

長さ 4 では $k = 1, 2, 3$ の 3 通りがあります。
$N (1, 4) = N (1, 1) N (2, 4) + N (1, 2) N (3, 4) + N (1, 3) N (4, 4) = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$ 。

【手順 5】全体の欄の開始記号の値は $N_{S} (1, 4) = 5$ なので、導出木は 5 個あります。これは、4 個の $a$ に括弧を付けて 2 つずつまとめる次の 5 通りに対応しています： $((aa) a) a$ , $(a (aa)) a$ , $(aa) (aa)$ , $a ((aa) a)$ , $a (a (aa))$ 。

答え: $5$

よくある誤り

CYK 法と同じく「生成できれば 1」と記録してしまう誤り。これでは例題の答えが $1$ になる。正しくは個数を記録して足し合わせる。たとえば $N (1, 3) = 1 + 1 = 2$ とする。
左右の個数を掛けずに足してしまう誤り。例題の $k = 1$ の項を $N (1, 1) + N (2, 4) = 3$ とすると、 $N (1, 4)$ が $5$ にならない。左右の部分木は独立に選べるので、正しくは $N (1, 1) \cdot N (2, 4) = 2$ 。
分割位置 $k$ や規則の一部を落とす誤り。たとえば真ん中の $k = 2$ だけを使うと $N (1, 4) = N (1, 2) N (3, 4) = 1$ になる。正しくは、 $i \leq k \leq j - 1$ のすべての $k$ と、 $X$ を左辺とするすべての規則 $X \to Y Z$ について和をとる。
全体の欄にあるすべての非終端記号の値を合計してしまう誤り。たとえば $N_{S} (1, n) + N_{A} (1, n)$ とする。正しくは、 $w$ の導出木の個数は開始記号の値 $N_{S} (1, n)$ だけである。

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

導出木の個数の数え上げ

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題