所属判定問題 CYK法
・Gを文脈自由文法とする。入力としてw∈T^*が与えられたとき、w∈L(G)であるかどうかを判定するアルゴリズムがある。
証明：
Gについて、A⇒^*εとなるような生成規則を取り除いていけばε∈L(G)かどうかを判定できる。さらにεがあるなら、L(G)-{ε}を生成するChomsky標準形の文脈自由文法G'を作ることができる。Chomsky標準形の生成規則を前提として、次のアルゴリズムによってw=x_1,...,x_nがw∈L(G')かどうかを判定する。
for i = 1 to n
V_i1 <- {A | A -> a∈P, xi = a}
next
for j = 2 to n //j=3
for i = 1 to n-j+1 //i=1
V_ij = φ
for k = 1 to j-1 //k=1
V_ij = V_ij ∪
{A | A -> BC∈P, B∈V_ik, C∈V_{i+k,j-k}}/V_11,V_22
next
next
next
これは動的計画法の一種。
上記のようにfor文を書くとわかりづらいが、実質は以下の表のようになっている。
生成規則を
S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a
とする。w=baabaとして、上記の規則から生成されるか調べる。
[j]
5 S,A,C
4 * | S,A,C
3 * | B | B
2 S,A | B | S,C | S,A
1 B | A,C | A,C | B | A,C
b | a | a | b | a
1 2 3 4 5 [i]
■1-0
まずbaabaに対応する変数に変える。左の数字はi-jに対応。
・1-1~5-1 baaba->B[AC][AC]B[AC]
baabaに対応する変数に戻す。
■2-0
隣接する2変数を1変数に縮めようと試みる。1,2文字目から4,5文字目までの4パターンを考える。
・2-1 B[AC][AC]B[AC]->[AS][AC]B[AC]
1,2文字目のBAかBCを戻す。BA->AかBC->Sになる。
・2-2 B[AC][AC]B[AC]->BBB[AC]
2,3文字目のAAかACかCCを戻す。CC->Bになる。
・2-3 B[AC][AC]B[AC]->B[AC][SC][AC]
3,4文字目のABかCBを戻す。AB->S,Cになる。
・2-4 B[AC][AC]B[AC]->B[AC][AC][AS]
4,5文字目のBAかBCを戻す。BA->AかBC->Sになる。
■3-0
2-0で2変数->1変数にしたものと、その隣接の1変数の組み合わせについて考える。
・3-1 [AS][AC]B[AC]->*、 BBB[AC]->*
候補になるのは初期1,2文字目を戻した[AS]と初期3文字目の[AC]だが、[AS][AC]を生成する規則はない。
もうひとつの候補は初期1文字目のBと初期2,3文字目を戻したBだが、BBを生成する規則はない。
・3-2 BBB[AC]->*、 B[AC][SC][AC]->BB[AC]
候補になるのは初期2,3文字目を戻したBと初期4文字目のBだが、BBを生成する規則はない。
もうひとつの候補は初期2文字目の[AC]と初期3,4文字目を戻した[SC]であり、[AC][SC]を生成するのはBである。
・3-3 B[AC][SC][AC]->B[AC]B、 B[AC][AC][AS]->*
候補になるのは初期3,4文字目を戻した[SC]と初期5文字目の[AC]であり、[SC][AC]を生成する変数はBである。
もうひとつの候補は初期3文字目の[AC]と初期4,5文字目を戻した[AS]だが、[AC][SC]を生成する規則はない。
■4-0
ここから少しわかりづらい。連続した4変数を生成するような1変数の候補を考えることになる。たとえば[1文字目]と[2-4文字目の圧縮]を生成する規則があるか、[1-2文字目の圧縮]と[3-4文字目の圧縮]を生成する規則があるか、[1-3文字目の圧縮]と[4文字目]を生成する規則があるか、の3通りを考える。
・4-1 BB[AC]->*、 [AS][SC][AC]->*、 *->*
[1][2-4]も[1-2][3-4]も[1-3][4]も生成する規則がない。
・4-2 B[AC]B->B[SC]、 BB[AS]->BA、 BB[AC]->BA
[2][3-5]も[2-3][4-5]も[2-4][5]も生成する規則がある。
■5-0
4-0と同様に候補を探す。5-1だけであり、[1][2-5],[1-2][3-5],[1-3][4-5],[1-4][5]の4通り考えればよい。
・5-1 B[SAC]->[AS]、 [AS]B->[SC]、 *->*、 *->*
[1][2-5]か[1-2][3-5]でSが出てくることがわかる。
