CYK法
CYK法(英: CYK algorithm)は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略(それぞれ、RISCの先駆と言われる801などでも知られるジョン・コック、Daniel Younger、嵩忠雄である)。文脈自由文法の構文解析手法と捉えることもできる。このアルゴリズムは一種の動的計画法である。
標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。
CYK法の最悪時間計算量は Θ(n) であり、n は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。
形式的でない説明をするなら、このアルゴリズムは単語の並びについて、考えられるあらゆる組合せを考慮し、与えられた文字列の i 番目から長さ j の並びが Rk から生成される場合に P[i,j,k] を true にセットする。長さ 1 の並びを検討したら、次に長さ 2 の並びというように検討していく。長さ 2 以上の並びの場合、その並びを2つに分け(分け方を様々に変えて)、P → Q R という生成規則で Q と R がその並びの前半部分と後半部分にマッチするかどうかを調べる。マッチする場合、P をその並び全体にマッチするものとして記録する。この一連の処理が完了すると、入力文字列全体を含む記号の並びが開始記号から生成されるかどうかが判定できる。