4. CYK 分析¶
4.1. CYK 分析¶
由 J. Cocke、D.H. Younger 和 T. Kasami 发明
分析串 \(w\) 需要 \(|w|^3\) 步。
动态规划 会记住小的子问题的答案， 这样就不必再次求解它们。
对于 CYK 分析，文法必须首先处于 Chomsky 范式（CNF）中。
定义（Definition）： 如果 CFG 的所有产生式都具有以下形式，则该 CFG 是 Chomsky 范式（CNF）的
\(A \rightarrow BC\) 或 \(A \rightarrow a\)
其中 \(A, B, C \in V\) 且 \(a \in T\)。
4.1.1. CYK 分析算法¶
假设 \(G = (V, T, S, P)\) 是 CNF 的，并且 \(w =
a_1a_2...a_n\)。
定义子串 \(w_{ij} = a_i...a_j\)。
定义子集
\(V, V_{ij} = \{A \in V \mid A \stackrel{*}{\Rightarrow} w_{ij} \}\)
那么当且仅当 \(S \in V_{1n}\) 时 \(w \in L(G)\)。
备注
当且仅当存在什么样的产生式时， \(A \in V_{ii}\) ？
答案： \(A \rightarrow a_i\)
所有 \(V_{ii}\) 都很容易，只需看是否存在某条产生式即可。
注意：计算 \(V_{ij}\)。
对于 \(j >i\) ，当且仅当存在一条产生式 \(A \rightarrow BC\)
满足对某个满足 \(i \le k, k < j\) 的 \(k\) 有
\(B \stackrel{*}{\Rightarrow} w_{ik}\) 且
\(C \stackrel{*}{\Rightarrow} w_{{k+1}j}\) 时，
\(A\) 才推导出 \(w_{ij}\)。
4.1.2. 算法¶
计算 \(V_{11}, V_{22}, V_{33}, \ldots, V_{nn}\)
计算 \(V_{12}, V_{23}, V_{34}, \ldots, V_{{n-1}n}\)
计算 \(V_{13}, V_{24}, V_{35}, \ldots, V_{{n-2}n}\)
\(\ldots\)
最后一步是？计算 \(V_{1n}\)
我们怎么知道它是否有效？ 如果最后一步是 \(S\)
