CYK

CYK法 は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。