チョムスキー標準形の文脈自由文法について、長さ n の記号列がその文法から導出できるかを判定する CYK 法の時間計算量はどれか。ここで、文法の大きさは定数とみなす。

解説

正解は「$O(n^3)$」です。CYK 法は動的計画法の一種で、入力の各部分列について、それを導出できる非終端記号の集合を表に記録します。部分列は約 $n^2/2$ 個あり、それぞれについて2つに分ける位置を最大 n−1 通り調べ、規則 A → BC を当てはめるので、全体で $O(n^3)$ になります。「$O(n)$」は、有限オートマトンで正規言語を判定する場合や、LR 法など決定性の構文解析で達成できる計算量です。「$O(n^2)$」は部分列の数だけを数えたもので、分割位置の試行を見落としています。「$O(2^n)$」は、すべての導出を総当たりする場合に近い計算量です。