F.5 语法等价性与范式 - SLP3 中文翻译

形式语言被定义为一个（可能无限的）词串集合。由此可以提出一种判断两个语法是否等价的方法：看它们是否生成相同的字符串集合。事实上，两个彼此不同的上下文无关语法完全可能生成同一种语言。

通常区分两类语法等价性：弱等价与强等价。如果两个语法生成相同的字符串集合，并且为每个句子指派相同的短语结构（只允许非终结符号名称不同），它们就是强等价的。如果两个语法生成相同的字符串集合，但并不为每个句子指派相同的短语结构，它们就是弱等价的。

有时，让语法采用某种范式（normal form）很有用，在范式中，每个产生式都具有特定形式。例如，如果一个上下文无关语法不含 $\epsilon$ ，而且每个产生式都具有 $A\to BC$ 或 $A\to a$ 的形式，那么它就采用乔姆斯基范式（Chomsky normal form，CNF；Chomsky, 1963）。也就是说，每条规则的右侧要么有两个非终结符，要么有一个终结符。乔姆斯基范式语法是二叉分支的，即它具有二叉树结构（一直到词汇前节点）。第 19 章的 CKY 句法分析算法将利用这一二叉分支性质。

任何上下文无关语法都可以转换成与其弱等价的乔姆斯基范式语法。例如，形如

A\to BCD

的规则可以转换成下面两条 CNF 规则（练习 F.8 要求读者写出完整算法）：

A\to BX

X\to CD

有时，使用二叉分支实际上还能产生更小的语法。例如，可概括为

VP\to VBD\ NP\ PP^*

的句子，在宾州树库中由下面一系列规则表示：

\begin{aligned} VP&\to VBD\ NP\ PP\\ VP&\to VBD\ NP\ PP\ PP\\ VP&\to VBD\ NP\ PP\ PP\ PP\\ VP&\to VBD\ NP\ PP\ PP\ PP\ PP\\ &\quad\ldots \end{aligned}

但也可以用下列两条规则的语法生成：

VP\to VBD\ NP\ PP

VP\to VP\ PP

用 $A\to AB$ 形式的规则生成符号 A 后接一个可能无限长的符号 B 序列，称为乔姆斯基附接（Chomsky adjunction）。