CKYは実際にCNFを必要としますか？

Question

私はCYK/CKYアルゴリズムが文法がChomsky Normal Form（CNF）であることを要求するいくつかの場所を読んだ。

CYKの標準バージョンのみチョムスキー標準形（CNF）に与えられた文脈自由文法 で動作〜Wikipedia

しかし、私はまた、どこCKYアルゴリズムの多くの例を見てきました文法はCNFにはありませんでした。私ものRHSに3つの非端子を使用CKYを実証する他の例を見てきました

S -> NP VP [0.9] 
S -> VP [0.1] 
VP -> V NP [0.4] 
Vp -> V [0.6] 
... 

：単項のルールが含まれています：クリストファー・マニングが使用する一般的な例は、「魚の人々の水槽」（PPT slide #19参照）であります生産（例：VP -> Verb NP NPreference）。なぜ矛盾？

Answer 1

CYKのランタイムは、長さkの生産のためにストリングをk個の部分に分解するすべての可能な方法を考慮しているため、最も長い生産ルールの長さに依存します。これは、フェーズごとのランタイムがO（n ^k）であることを意味します。ここで、kは最長生産の長さです。 O（n）フェーズがあるので、最大生産長kを持つ文法上のCYKのランタイムはO（n ^{k + 1}）です。

CYKはCNFにはない文法では正しく動作しますが、実行時は文字列の長さが3立方体にならないことがあります。 CNF要件はk = 2を強制するだけであり、O（n ）の全体的な実行時間を保証します。