CYK Algorithm 的唯一目的可以概括成一句话：

给定一个已经转换成 CNF 的文法 G 和一个字符串 w，判断 w 是否能够由 G 生成。

换句话说，它回答的是：

“这个字符串属于 Language(G) 吗？”

---

• CYK Algorithm Made Easy (Parsing) - YouTube

计算理论：CYK 算法全景手写笔记整理与纠错指南

知识网络引入：CYK 算法的生态位

在计算理论中，我们经常遇到以下三个核心概念：

1. 上下文无关文法（Context-Free Grammar, CFG）：用于定义语言的结构。

2. 乔姆斯基范式（Chomsky Normal Form, CNF）：CFG 的一种标准化形式，所有规则非黑即白（要么产生两个非终结符，要么产生一个终结符）。

3. 成员资格问题（Membership Problem）：判断一个给定的字符串 $w$ 是否属于文法 $G$ 所生成的语言 $L(G)$（即 $w \in L(G)$？）。

对于简短的字符串，我们可以通过尝试推导（Derivation）来判断；然而，当字符串长度增长、文法规则变得极为复杂时，盲目的试错会导致推导树呈指数级爆炸。CYK 算法（Cocke-Younger-Kasami Algorithm） 正是解决这一痛点的利器。它利用 动态规划（Dynamic Programming） 的思想，在多项式时间 $O(n^3 \cdot |G|)$ 内系统化地解决成员资格问题。

第一部分：CYK 算法的底层逻辑

1. 为什么必须将文法转换为 CNF？

CNF（乔姆斯基范式）的产生式规则极其严苛，仅允许以下两种形式：

• $A \to BC$ （一个非终结符推导出恰好两个非终结符）

• $A \to a$ （一个非终结符推导出恰好一个终结符）

这种高度统一的结构带来了一个巨大的数学优势：任何能够由该文法生成的字符串，其语法分析树（Parsing Tree）在本质上都是一棵二叉树。

        S
       / \
      A   B
     / \   \
    a   b   c

因为是二叉树，所以任何长度大于 1 的子串，最终一定可以被切分成左、右两个半部分。这使得我们可以采用“自底向上”的动态规划策略：先算出短区间的生成变量，再通过合并相邻区间去推导长区间的生成变量。

2. CYK 三角形表格的几何结构

对于一个长度为 $n$ 的字符串 $w = w_1 w_2 \dots w_n$，CYK 算法会建立一个大小为 $n \times n$ 的上三角表格。

高度 (子串长度)
  ^
  |      [ 长度 n：整个字符串 w ]  <-- 检查此格是否包含开始符号 S
  |       /                    \
  |   [ 长度 2 ]           [ 长度 2 ]
  |     /    \               /    \
  |  [w_1]   [w_2]  .......[w_{n-1}] [w_n]  <-- 最底层：长度 1 的单个字符
  +--------------------------------------------> 字符串位置

• 最底层（第 1 层）：对应长度为 $1$ 的子串（即单个字符 $w_i$）。

• 中间层（第 $l$ 层）：对应长度为 $l$ 的子串。

• 最顶层（第 $n$ 层）：对应整个字符串 $w$。

• 判定标准：当且仅当最顶层的集合中包含文法的开始符号 $S$ 时，该字符串被接受（Accept），否则被拒绝（Reject）。

第二部分：CYK 填表的核心算法步骤

步骤一：初始化最底层（长度 $l = 1$）

对于字符串中的每一个字符 $w_i$（其中 $1 \le i \le n$），在对应的表格单元格 $T[1, i]$ 中填入所有能够一步推导出该字符的非终结符集合：

$T[1, i] = \{ A \mid A \to w_i \in P \}$

步骤二：自底向上迭代填表（长度 $l \ge 2$）

对于子串长度 $l$ 从 $2$ 逐步增加到 $n$：

1. 确定子串起点 $i$（子串范围为 $w_i \dots w_{i+l-1}$）。

2. 枚举所有的切分点 $k$（其中 $1 \le k < l$），将当前子串划分为左、右两部分：

   • 左半部分：长度为 $k$，起始位置为 $i$ $\to$ 对应单元格 $T[k, i]$。

   • 右半部分：长度为 $l-k$，起始位置为 $i+k$ $\to$ 对应单元格 $T[l-k, i+k]$。

3. 计算左右集合的笛卡尔积（严格保序），并查找文法规则：

   $T[l, i] = \bigcup_{k=1}^{l-1} \{ A \mid A \to B C \in P, \text{ 且 } B \in T[k, i], C \in T[l-k, i+k] \}$

第三部分：手写计算的关键痛点与避坑指南

在人工手算 CYK 过程中，极易在以下四个细节上出错。请务必牢记这些核心口诀：

1. 笛卡尔积的“保序性”（方向不能交换！）

非终结符的合并是严格区分左右顺序的。因为在 CNF 中，产生式 $A \to BC$ 与 $A \to CB$ 是完全不同的规则。

• 标准计算流：若左格为 $L = \{S, C\}$，右格为 $R = \{A, C\}$，则我们需要检查的配对为：

  $L \times R = \{(S,A), (S,C), (C,A), (C,C)\}$

  绝对不能将其写成 $(A,S)$ 或 $(C,S)$。

2. 多切分点的“并集法则”

当子串长度 $l \ge 3$ 时，会有多个切分点。例如长度为 3 的子串 aba，有两种切分方式：

• 切法①（a | ba）：左格（长度1） $\times$ 右格（长度2） $\to T[1, 1] \times T[2, 2]$

• 切法②（ab | a）：左格（长度2） $\times$ 右格（长度1） $\to T[2, 1] \times T[1, 3]$

必须计算出所有切法对应的变量集合，然后取并集（Union）填入当前空格中。 遗漏任何一种切法都会导致最顶层结果不完整。

3. 空集 $\emptyset$ 的传递性

如果某个格子在计算后没有任何规则匹配，应当填入空集符号 $\emptyset$。

• 在后续计算中，任何集合与空集 $\emptyset$ 进行笛卡尔积，结果仍然是空集：

  $A \times \emptyset = \emptyset$

4. 纠错：原始材料中的笔误

在一些复习课件（如您上传的文件第 6 页、第 10 页）中，曾出现以下描述：

(2,3) “bb” 的合并： 左右分别是 $\{B\}$ 与 $\{B\}$，组合 $(B, B)$，文法中有 $B \to CC$，因此得到 $\{B\}$。

这是典型的笔误！ 在数学逻辑上，组合 $(B,B)$ 只能匹配形式为 $X \to BB$ 的产生式。文法规则 $B \to CC$ 的右侧是 $CC$，因此它匹配的组合应该是 $(C,C)$。 在手算时，请务必保持严谨：只有当组合中的符号与文法产生式右侧完全一致时，才能推导出左侧的变量。

第四部分：渐进式练习题集（含保姆级推导）

练习题 1：基础热身

文法 $G_1$ (CNF)：

$S \to AB, \quad A \to a, \quad B \to b$

待判定字符串： $w = abb$（长度 $n = 3$）

分步求解过程：

1. 第 1 层（长度 1）：

   • $w_1 = a \to$ 匹配 $A \to a \to \{A\}$

   • $w_2 = b \to$ 匹配 $B \to b \to \{B\}$

   • $w_3 = b \to$ 匹配 $B \to b \to \{B\}$

2. 第 2 层（长度 2）：

   • 子串 ab（区间 1~2）：左 a $\{A\}$ $\times$ 右 b $\{B\}$ $\to (A,B)$。

     • 查文法：存在 $S \to AB$。因此该格填 $\{S\}$。

   • 子串 bb（区间 2~3）：左 b $\{B\}$ $\times$ 右 b $\{B\}$ $\to (B,B)$。

     • 查文法：不存在任何产生式右侧为 $BB$。因此该格填 $\emptyset$。

3. 第 3 层（长度 3，子串 abb）：

   • 切法①（a | bb）：左 a $T[1,1]=\{A\}$ $\times$ 右 bb $T[2,2]=\emptyset \to \emptyset$。

   • 切法②（ab | b）：左 ab $T[2,1]=\{S\}$ $\times$ 右 b $T[1,3]=\{B\} \to (S,B)$。

     • 查文法：不存在 $X \to SB$。因此贡献为 $\emptyset$。

   • 并集：$\emptyset \cup \emptyset = \emptyset$。

最终 CYK 三角表格：

层 3 (abb):     [   \emptyset   ]
层 2 (ab, bb):  [ {S} ]   [  \emptyset  ]
层 1 (a, b, b): [ {A} ]   [ {B} ]   [ {B} ]
                 w_1=a     w_2=b     w_3=b

结论：最顶层单元格不包含开始符号 $S$，因此字符串 $abb \notin L(G_1)$ （Reject）。

练习题 2：多重规则匹配

文法 $G_2$ (CNF)：

$S \to AB \mid BC, \quad A \to a, \quad B \to b, \quad C \to AB$

待判定字符串： $w = ab$（长度 $n = 2$）

分步求解过程：

1. 第 1 层（长度 1）：

   • $w_1 = a \to \{A\}$

   • $w_2 = b \to \{B\}$

2. 第 2 层（长度 2，子串 ab）：

   • 左 $\{A\}$ $\times$ 右 $\{B\} \to (A,B)$。

   • 查文法：发现同时存在 $S \to AB$ 和 $C \to AB$。

   • 重要纠错提醒：此时必须将 $S$ 和 $C$ 全部放入格子中，不能遗漏！

   • 结果：$\{S, C\}$。

最终 CYK 三角表格：

层 2 (ab):    [ {S, C} ]
层 1 (a, b):  [  {A}  ]  [  {B}  ]
               w_1=a      w_2=b

结论：最顶格包含开始符号 $S$，因此字符串 $ab \in L(G_2)$ （Accept）。

练习题 3：引入空集的并集计算

文法 $G_3$ (CNF)：

$S \to AB \mid BC, \quad A \to a, \quad B \to CC \mid b, \quad C \to a$

待判定字符串： $w = abb$（长度 $n = 3$）

分步求解过程：

1. 第 1 层（长度 1）：

   • $w_1 = a \to$ 匹配 $A \to a$ 与 $C \to a \to \{A, C\}$

   • $w_2 = b \to$ 匹配 $B \to b \to \{B\}$

   • $w_3 = b \to$ 匹配 $B \to b \to \{B\}$

2. 第 2 层（长度 2）：

   • 子串 ab（区间 1~2）：左 $\{A,C\}$ $\times$ 右 $\{B\} \to \{(A,B), (C,B)\}$。

     • 查文法：存在 $S \to AB$，无 $X \to CB$。结果：$\{S\}$。

   • 子串 bb（区间 2~3）：左 $\{B\}$ $\times$ 右 $\{B\} \to \{(B,B)\}$。

     • 查文法：无任何规则。结果：$\emptyset$。

3. 第 3 层（长度 3，子串 abb）：

   • 切法①（a | bb）：左 $T[1,1]=\{A,C\}$ $\times$ 右 $T[2,2]=\emptyset \to \emptyset$。

   • 切法②（ab | b）：左 $T[2,1]=\{S\}$ $\times$ 右 $T[1,3]=\{B\} \to \{(S,B)\}$。

     • 查文法：无。结果：$\emptyset$。

   • 并集：$\emptyset \cup \emptyset = \emptyset$。

最终 CYK 三角表格：

层 3 (abb):     [   \emptyset   ]
层 2 (ab, bb):  [ {S} ]   [  \emptyset  ]
层 1 (a, b, b): [ {A, C} ] [ {B} ]   [ {B} ]
                 w_1=a     w_2=b     w_3=b

结论：最顶格不含 $S$，字符串被拒绝（Reject）。

练习题 4：完全体 3 阶演练（感受笛卡尔积顺序的重要性）

文法 $G_4$ (CNF)：

$S \to AB \mid BC, \quad A \to BA \mid a, \quad B \to CC \mid b, \quad C \to AB \mid a$

待判定字符串： $w = aba$（长度 $n = 3$）

分步求解过程：

1. 第 1 层（长度 1）：

   • $w_1 = a \to \{A, C\}$

   • $w_2 = b \to \{B\}$

   • $w_3 = a \to \{A, C\}$

2. 第 2 层（长度 2）：

   • 子串 ab（区间 1~2）：左 $\{A, C\}$ $\times$ 右 $\{B\} \to \{(A,B), (C,B)\}$。

     • 查文法：存在 $S \to AB$ 与 $C \to AB$。结果：$\{S, C\}$。

   • 子串 ba（区间 2~3）：左 $\{B\}$ $\times$ 右 $\{A, C\} \to \{(B,A), (B,C)\}$。

     • 查文法：存在 $A \to BA$ 与 $S \to BC$。结果：$\{A, S\}$。

     • 思考：注意看，这里的左右顺序若写反了，匹配出的结果会大相径庭！

3. 第 3 层（长度 3，子串 aba）：

   • 切法①（a | ba）：左 $T[1,1]=\{A,C\}$ $\times$ 右 $T[2,2]=\{A,S\}$

     • 笛卡尔积组合：$\{(A,A), (A,S), (C,A), (C,S)\}$。

     • 查文法：没有任何产生式右端符合这些组合。贡献：$\emptyset$。

   • 切法②（ab | a）：左 $T[2,1]=\{S,C\}$ $\times$ 右 $T[1,3]=\{A,C\}$

     • 笛卡尔积组合：$\{(S,A), (S,C), (C,A), (C,C)\}$。

     • 查文法：发现 $B \to CC$ 符合 $(C,C)$ 组合！贡献：$\{B\}$。

   • 并集合并：$\emptyset \cup \{B\} = \{B\}$。

最终 CYK 三角表格：

层 3 (aba):     [    {B}    ]
层 2 (ab, ba):  [ {S, C} ]  [ {A, S} ]
层 1 (a, b, a): [ {A, C} ]  [  {B}  ]  [ {A, C} ]
                 w_1=a       w_2=b      w_3=a

结论：顶格为 $\{B\}$，不包含开始符号 $S$，因此 $aba \notin L(G_4)$ （Reject）。

第五部分：终极挑战 —— 日本名校（阪大/九大）研究生入学真题风格演练

现在，我们直接挑战难度与名校研究生入学考试完全一致的 4 阶字符串判定题。通过此题，您将彻底巩固长字符串的切分逻辑。

真题模拟

文法 $G_{\text{exam}}$ (CNF)：

$S \to AB \mid BC, \quad A \to BA \mid a, \quad B \to CC \mid b, \quad C \to AB \mid a$

待判定字符串： $w = abba$（长度 $n = 4$）

我们需要计算一个 $4 \times 4$ 的三角形表。表格的横轴为字符串的索引 $i \in [1, 4]$，纵轴为子串长度 $l \in [1, 4]$。我们用坐标 $(l, i)$ 来表示第 $l$ 层、起点为 $i$ 的单元格。

                  (4, 1) [整个串 abba]
                  /                  \
            (3, 1) [abb]          (3, 2) [bba]
            /          \          /          \
      (2, 1) [ab]    (2, 2) [bb]    (2, 3) [ba]
      /         \    /         \    /         \
(1,1)[a]   (1,2)[b]   (1,3)[b]   (1,4)[a]

详细计算步骤：

1. 长度 $l = 1$ （最底层）

• $(1, 1)$ 子串 a：由于 $A \to a, C \to a \implies \mathbf{\{A, C\}}$

• $(1, 2)$ 子串 b：由于 $B \to b \implies \mathbf{\{B\}}$

• $(1, 3)$ 子串 b：由于 $B \to b \implies \mathbf{\{B\}}$

• $(1, 4)$ 子串 a：由于 $A \to a, C \to a \implies \mathbf{\{A, C\}}$

2. 长度 $l = 2$

• $(2, 1)$ 子串 ab：结合自 $(1, 1)$ 和 $(1, 2)$。

  • $T[1, 1] \times T[1, 2] = \{A, C\} \times \{B\} = \{(A,B), (C,B)\}$

  • 查文法规则：$S \to AB, C \to AB$ 匹配 $(A,B)$。

  • 结果：$\mathbf{\{S, C\}}$

• $(2, 2)$ 子串 bb：结合自 $(1, 2)$ 和 $(1, 3)$。

  • $T[1, 2] \times T[1, 3] = \{B\} \times \{B\} = \{(B,B)\}$

  • 查文法规则：无任何规则右端为 $BB$。

  • 结果：$\mathbf{\emptyset}$

• $(2, 3)$ 子串 ba：结合自 $(1, 3)$ 和 $(1, 4)$。

  • $T[1, 3] \times T[1, 4] = \{B\} \times \{A, C\} = \{(B,A), (B,C)\}$

  • 查文法规则：$A \to BA$ 匹配 $(B,A)$；$S \to BC$ 匹配 $(B,C)$。

  • 结果：$\mathbf{\{A, S\}}$

3. 长度 $l = 3$

• $(3, 1)$ 子串 abb：有两种切法。

  • 切法一（a | bb）：$T[1,1] \times T[2,2] = \{A,C\} \times \emptyset = \emptyset$

  • 切法二（ab | b）：$T[2,1] \times T[1,3] = \{S,C\} \times \{B\} = \{(S,B), (C,B)\}$。无匹配规则 $\to \emptyset$。

  • 并集结果：$\mathbf{\emptyset}$

• $(3, 2)$ 子串 bba：有两种切法。

  • 切法一（b | ba）：$T[1,2] \times T[2,3] = \{B\} \times \{A,S\} = \{(B,A), (B,S)\}$。$A \to BA$ 匹配 $(B,A)$ $\to \{A\}$。

  • 切法二（bb | a）：$T[2,2] \times T[1,4] = \emptyset \times \{A,C\} = \emptyset$。

  • 并集结果：$\mathbf{\{A\}}$

4. 长度 $l = 4$（顶层，子串 abba）

有三种切法，必须全部枚举并求并集：

• 切法一（a | bba）：

  $T[1,1] \times T[3,2] = \{A,C\} \times \{A\} = \{(A,A), (C,A)\}$

  查文法：无。贡献 = $\emptyset$。

• 切法二（ab | ba）：

  $T[2,1] \times T[2,3] = \{S,C\} \times \{A,S\} = \{(S,A), (S,S), (C,A), (C,S)\}$

  查文法：无。贡献 = $\emptyset$。

• 切法三（abb | a）：

  $T[3,1] \times T[1,4] = \emptyset \times \{A,C\} = \emptyset$

  贡献 = $\emptyset$。

• 合并所有切法的并集：

  $T[4, 1] = \emptyset \cup \emptyset \cup \emptyset = \mathbf{\emptyset}$

最终完美考试真题 CYK 三角表：

结论：最顶层单元格为空集 $\emptyset$，并不包含开始符号 $S$。因此，字符串 $abba \notin L(G_{\text{exam}})$（Reject）。

💡 复习总结与黄金心智模型

做完这套题后，请在脑海中牢固建立以下思维模型：

1. 不要试图正向推导：CYK 是一个自底向上的区间合并过程。我们先解决“单字由谁生成”，再解决“两字小区间由谁生成”，最终递推至整个大区间。

2. 三步走机械流水线：

   $\text{切分 (Split)} \longrightarrow \text{严格保序组合 (Combine)} \longrightarrow \text{查阅规则 (Lookup)}$

3. 考前闭眼默诵口诀：

   • “左格元素永远在前，右格元素永远在后。”

   • “有多条切分线时，各线计算结果要取并集。”

   • “不能因为暂时推不出，就强行凑出一个变量，无对应规则时果断填空集 $\emptyset$。”