CYK 法

チョムスキー標準形の文法について、部分文字列 $w_{i .. j}$ を生成する非終端記号の集合の表を短い部分文字列から順に埋め、 $S$ が全体の欄に入るかで $w$ が生成されるかを判定できる

前提

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

説明

CYK 法（Cocke–Younger–Kasami 法）は、文脈自由文法と文字列 $w$ が与えられたとき、 $w$ がその文法で生成されるかを機械的に判定する方法です。導出をあれこれ試す必要はなく、「どの部分文字列をどの非終端記号が生成できるか」を表にまとめ、短い部分文字列から長い部分文字列へ順に埋めていきます。対象は、次に定義するチョムスキー標準形の文法です。プログラミング言語の構文解析や、文法の問題を確実に判定したい場面で使います。

なぜそうしてよいのか

チョムスキー標準形とは、すべての生成規則が $X \to Y Z$ （ $Y, Z$ は非終端記号）か $X \to a$ （ $a$ は終端記号）の形をしている文法のことです（空文字列を生成したいときだけ、 $S$ が右辺に現れないという条件のもとで $S \to ε$ を許します）。この形では、長さ $2$ 以上の文字列の導出木の根は必ず $X \to Y Z$ で 2 つに分かれます。 $ε$ を生成する規則がないので、 $Y$ と $Z$ はどちらも長さ $1$ 以上の文字列を生成します。つまり $X$ が $w_{i} w_{i + 1} \dots w_{j}$ を生成するのは、ある切れ目 $k$ （ $i \leq k \leq j - 1$ ）で文字列を前半 $w_{i .. k}$ と後半 $w_{k + 1.. j}$ に分け、 $Y$ が前半を、 $Z$ が後半を生成するときであり、そのときに限ります。

そこで $w = w_{1} w_{2} \dots w_{n}$ に対し、 $T [i, j] = {X ∣ X \Rightarrow^{*} w_{i .. j}}$ と定めます。長さ $1$ の欄は規則 $X \to w_{i}$ を見るだけで決まり、長さ $2$ 以上の欄は
$T [i, j] = k = i ⋃ j - 1 {X ∣ X \to Y Z が規則, Y \in T [i, k], Z \in T [k + 1, j]}$
で決まります。右辺に出てくるのは自分より短い部分文字列の欄だけなので、長さの短い順に埋めればすべての欄が正しく求まります（長さに関する帰納法）。

最後に、 $w$ 全体を $S$ から導出できること、つまり $S \in T [1, n]$ が「 $w$ が生成される」ことと同じです。欄は $\frac{n ( n + 1 )}{2}$ 個、各欄で切れ目を高々 $n - 1$ 通り調べるので、手間は $n^{3}$ 程度（に規則の数を掛けたもの）で済みます。

手順

文法がチョムスキー標準形（規則が $X \to Y Z$ か $X \to a$ のみ）であることを確かめ、 $w = w_{1} w_{2} \dots w_{n}$ （ $n \geq 1$ ）と番号を振る。空文字列については $S \to ε$ があるかどうかだけで判定する
長さ $1$ の欄を埋める： $T [i, i] = {X ∣ X \to w_{i} が規則}$
長さ $ℓ = 2, 3, \dots, n$ の順に、各 $T [i, j]$ （ $j = i + ℓ - 1$ ）を埋める。切れ目 $k = i, \dots, j - 1$ のすべてについて、 $Y \in T [i, k]$ 、 $Z \in T [k + 1, j]$ となる組 $(Y, Z)$ を作り、規則 $X \to Y Z$ の左辺 $X$ をすべて $T [i, j]$ に入れる
全体の欄 $T [1, n]$ に $S$ が入っていれば $w$ は生成され、入っていなければ生成されないと判定する

例題

非終端記号 $S, A, B, C$ （開始記号 $S$ ）、終端記号 $a, b$ と、生成規則 $S \to A B ∣ A C$ 、 $C \to S B$ 、 $A \to a$ 、 $B \to b$ からなるチョムスキー標準形の文法を考える。文字列 $w = aabb$ について CYK 法の表 $T [i, j]$ （ $1 \leq i \leq j \leq 4$ ）を埋めたとき、 $S$ を含む欄の個数を求めよ。

例題の解答

【手順 1】すべての規則が $X \to Y Z$ か $X \to a$ の形なので、チョムスキー標準形である。 $w_{1} = a, w_{2} = a, w_{3} = b, w_{4} = b$ 、 $n = 4$ 。

【手順 2】長さ 1： $A \to a$ 、 $B \to b$ より $T [1, 1] = {A}$ 、 $T [2, 2] = {A}$ 、 $T [3, 3] = {B}$ 、 $T [4, 4] = {B}$ 。

【手順 3】長さ 2：
・ $T [1, 2]$ ： $k = 1$ で組は $(A, A)$ 。右辺が $AA$ の規則はないので $T [1, 2] = \emptyset$ 。
・ $T [2, 3]$ ： $k = 2$ で組は $(A, B)$ 。 $S \to A B$ より $T [2, 3] = {S}$ 。
・ $T [3, 4]$ ：組は $(B, B)$ 。該当する規則はないので $\emptyset$ 。

長さ 3：
・ $T [1, 3]$ ： $k = 1$ で $T [1, 1]$ と $T [2, 3]$ から組 $(A, S)$ ができるが、右辺が $A S$ の規則はない。 $k = 2$ は $T [1, 2] = \emptyset$ なので組ができない。よって $T [1, 3] = \emptyset$ 。
・ $T [2, 4]$ ： $k = 2$ は $T [3, 4] = \emptyset$ なので組ができない。 $k = 3$ で $T [2, 3]$ と $T [4, 4]$ から組 $(S, B)$ ができ、 $C \to S B$ より $C$ が入る。よって $T [2, 4] = {C}$ 。

長さ 4：
・ $T [1, 4]$ ： $k = 1$ で $T [1, 1]$ と $T [2, 4]$ から組 $(A, C)$ ができ、 $S \to A C$ より $S$ が入る。 $k = 2$ は $T [1, 2] = T [3, 4] = \emptyset$ 、 $k = 3$ は $T [1, 3] = \emptyset$ なので何も加わらない。よって $T [1, 4] = {S}$ 。

【手順 4】 $S \in T [1, 4]$ なので、 $aabb$ はこの文法で生成される。

$S$ を含む欄は $T [2, 3]$ （部分文字列 $ab$ ）と $T [1, 4]$ （全体 $aabb$ ）の 2 個である。

答え: $2$

よくある誤り

組 $(Y, Z)$ の順序を逆にしてしまう誤り。正しくは、 $Y$ は前半の欄 $T [i, k]$ 、 $Z$ は後半の欄 $T [k + 1, j]$ から取る。例題で $T [2, 4]$ を求めるとき、組 $(S, B)$ は規則 $C \to S B$ に合うが、逆順の組 $(B, S)$ に合う規則はない。
切れ目 $k$ を 1 通り（たとえば $k = i$ だけ）しか調べない誤り。正しくは $k = i, i + 1, \dots, j - 1$ のすべてを調べる。例題の $T [2, 4]$ では、 $k = 2$ では何も入らず、 $k = 3$ で初めて $C$ が入る。
$S$ が $T [1, n]$ 以外の欄に入っていることを根拠に「 $w$ は生成される」と判定してしまう誤り。正しくは、全体の欄 $T [1, n]$ に $S$ が入るかどうかで判定する。例題の $S \in T [2, 3]$ は、部分文字列 $ab$ が生成されることを示すだけである。
チョムスキー標準形でない文法（ $X \to a B$ や $X \to Y$ 、 $X \to ε$ を含むもの）にそのまま適用してしまう誤り。正しくは、先に規則を $X \to Y Z$ と $X \to a$ の形だけにそろえてから使う。たとえば $X \to Y$ を残したまま表を作ると、 $Y$ が入る欄に $X$ を入れ忘れる。

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

入口の問題

この技能を使う問題

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

導出木の個数の数え上げ（大学数学オートマトン・形式言語）