乔姆斯基范式

接下来，我们将深入探讨上下文无关语言的封闭性及其他性质，开发出能够对任意上下文无关语言进行判定的算法，并最终引入一种非上下文无关的形式语言，从而引出第三类也是最后一类形式语言。我们首先介绍一种将任意上下文无关文法（CFG）转换为一种特殊形式——乔姆斯基范式（Chomsky Normal Form, CNF） 的方法，这有助于我们推导出关于上下文无关语言的一些重要结论。

乔姆斯基范式的准备工作

为了准备转换到乔姆斯基范式，我们需要对任何给定的上下文无关文法进行两项修改：

1. 在不改变所生成语言的前提下，移除所有规则中的空串 λ（除非原始语言包含空串，此时我们可能失去空串，但这是可以接受的特例）；
2. 移除单一产生式（unit productions），例如 $X \to Y$，同时保留其语法作用。

从实际应用角度看，移除 λ 具有重要意义。为了高效地判断一个字符串是否能被某上下文无关文法生成，在推导过程中，中间的句型最好不会缩短长度。如果某个变量可以用 λ 替换，那么当前推导串就可能变短，导致推导过程反复增长和收缩，效率低下。通过在不显式使用 λ 的情况下保留空串的语法效果，可以使句型长度不减少，这样的文法称为非收缩文法（noncontracting）。唯一的代价是修改后的文法不再生成空串，但这通常是一个无需特别关注的特殊情况。

移除空串 λ

为了在保留 λ 对非空字符串生成贡献的前提下将其移除，我们首先要识别出哪些变量可以直接或间接地生成空串。这类变量被称为可空变量（nullable variables）。一旦识别出来，我们就将这些变量的“可空效应”融入文法规则中，从而去除对 λ 的显式引用。修改后文法所识别的语言为 $L - \{\lambda\}$，其中 $L$ 是原文法所识别的语言。

以下面这个文法为例说明如何移除 λ：

\begin{align*} S & \to a ;|; Xb ;|; aYa \ X & \to Y ;|; \lambda \ Y & \to b ;|; X \end{align*}

变量 $X$ 是唯一直接推出 λ 的变量，但由于存在规则 $Y \to X$，因此 $Y$ 也是可空的。为了体现 $X$ 和 $Y$ 的可空性，我们对文法做如下调整：

\begin{align*} S & \to a ;|; Xb ;|; aYa ;|; b ;|; aa \ X & \to Y ;|; \lambda \ Y & \to b ;|; X \end{align*}

第一行中，我们在规则 $S \to Xb$ 中用 λ 替代 $X$，得到新规则 $S \to b$；同理，由于 $Y$ 可空，由 $S \to aYa$ 得到 $S \to aa$。我们的目标是彻底消除 λ，因此暂不处理最后两行中对 $X$ 或 $Y$ 使用 λ 的情况。在保留了可空变量的作用之后，我们现在可以完全删除 λ：

\begin{align*} S & \to a ;|; Xb ;|; aYa ;|; b ;|; aa \ X & \to Y \ Y & \to b ;|; X \end{align*}

由于原文法本就不生成空串，因此修改后的文法与原语言等价。若需要，我们还可以进一步简化：注意到 $X$ 等价于 $Y$，可将其消去：

\begin{align*} S & \to a ;|; Yb ;|; aYa ;|; b ;|; aa \ Y & \to b ;|; Y \end{align*}

像 $Y \to Y$ 这样的“自环规则”无意义，应予以删除：

\begin{align*} S & \to a ;|; Yb ;|; aYa ;|; b ;|; aa \ Y & \to b \end{align*}

最后，将 $Y \to b$ 回代入 $S$ 的规则中，得到：

$$S \to a \;|\; bb \;|\; aba \;|\; b \;|\; aa$$

由此可见，原看似复杂的文法实际上生成的是一个简单且有限的语言。

虽然在此例中较容易看出 $Y$ 是间接可空的，但在更复杂的文法中，我们需要一个系统化的算法来找出所有可空变量。下面的递归定义有助于设计这样的算法。

可空变量

• 若存在形如 $X \to \lambda$ 的规则，则变量 $X$ 是可空的；
• 若存在形如 $Y \to X_1X_2\cdots X_k$ 的规则，且所有右部变量 $X_i$ 都是可空的，则变量 $Y$ 也是可空的。

以上述文法为例，初始化可空变量集合 $\mathcal{N} = \{X\}$，因为有规则 $X \to \lambda$。接着利用第二条定义，寻找右部全由可空变量组成的规则，发现 $Y \to X$，于是将 $Y$ 加入集合，得 $\mathcal{N} = \{X, Y\}$。再检查是否存在仅含 $X$ 和/或 $Y$ 组成的右部规则，未发现新的，故确定只有 $X$ 和 $Y$ 是可空变量。

另一种更直观的方法是：创建文法副本，将所有直接可空变量替换为 λ，并重复此操作直至无法发现新的可空变量。以本例为例，已知 $X \to \lambda$ 表明 $X$ 可空，将所有 $X$ 替换为 λ：

\begin{align*} S & \to a ;|; b ;|; aYa \ X & \to Y ;|; \lambda \ Y & \to b ;|; \lambda \end{align*}

此时出现 $Y \to \lambda$，表明 $Y$ 也可空，继续将 $Y$ 替换为 λ：

\begin{align*} S & \to a ;|; b ;|; aa \ X & \to \lambda \ Y & \to b ;|; \lambda \end{align*}

没有新的可空关系产生，最终得出 $\mathcal{N} = \{X, Y\}$，结果一致。注意：这不是构造新文法，而是用于算法执行的临时操作，所得结果并不等价于原文法。

还有一个有用的技巧，用于在整个文法中传播可空变量的影响：对于每个可空变量 $V$，在其出现在规则右部（非单独出现）时，替换为表达式 $(V \;|\; \lambda)$，然后按照正则表达式代数展开。对当前例子，在原规则中对可空变量 $X$ 和 $Y$ 做如下替换：

\begin{align*} S & \to a ;|; (X ;|; \lambda)b ;|; a(Y ;|; \lambda)a \ X & \to Y ;|; \lambda \ Y & \to b ;|; X \end{align*}

展开第一行的表达式：

\begin{align*} S & \to a ;|; Xb ;|; \mathbf{b} ;|; aYa ;|; \mathbf{aa} \ X & \to Y ;|; \lambda \ Y & \to b ;|; X \end{align*}

示例

现在我们从以下文法中移除 λ，同时保留其生成非空串的效果：

\begin{align*} S & \to XYZ \ X & \to aXb ;|; Y \ Y & \to bY ;|; \lambda \ Z & \to ccZ ;|; Y \end{align*}

首先初始化可空变量集 $\mathcal{N} = \{Y\}$，并将所有规则中的 $Y$ 替换为 λ：

\begin{align*} S & \to XZ \ X & \to aXb ;|; \lambda \ Y & \to b ;|; \lambda \ Z & \to ccZ ;|; \lambda \end{align*}

可见 $X$ 和 $Z$ 也变为可空，故 $\mathcal{N} = \{X, Y, Z\}$，继续将 $X$ 和 $Z$ 替换为 λ：

\begin{align*} S & \to \lambda \ X & \to ab ;|; \lambda \ Y & \to b ;|; \lambda \ Z & \to cc ;|; \lambda \end{align*}

所有变量均为可空，因此 $\mathcal{N} = \{S, X, Y, Z\}$（尽管 $S$ 不出现在任何规则右部）。现在，在原规则中将每个可空变量 $V$ 出现的位置替换为 $(V \;|\; \lambda)$：

\begin{align*} S & \to (X ;|; \lambda)(Y ;|; \lambda)(Z ;|; \lambda) \ X & \to a(X ;|; \lambda)b ;|; Y \ Y & \to b(Y ;|; \lambda) ;|; \lambda \ Z & \to cc(Z ;|; \lambda) ;|; Y \end{align*}

展开并消除 λ 后，得到对应语言 $L - \{\lambda\}$ 的文法：

\begin{align*} S & \to XYZ ;|; XY ;|; XZ ;|; YZ ;|; X ;|; Y ;|; Z \ X & \to aXb ;|; ab ;|; Y \ Y & \to bY ;|; b \ Z & \to ccZ ;|; cc ;|; Y \end{align*}

由于 $S$ 不出现在任何规则右部，如有需要，我们可以重新添加 $S \to \lambda$，以恢复原语言中的空串。

移除单一产生式（Unit Productions）

单一产生式（如 $X \to Y$）效率较低，因为在推导过程中使用它并不会使中间句型增长。理想情况下，推导过程应单调增长，从而避免冗长的来回变换。与其使用 $X \to Y$，不如“跳过中间步骤”，直接将 $Y$ 所能生成的内容代入。

以前面示例中最终得到的非收缩文法为例，其中包含如下单一产生式：

\begin{align*} S & \to X ;|; Y ;|; Z \ X & \to Y \ Z & \to Y \end{align*}

借助单一产生式图（unit production graph），我们可以更清晰地理解这些规则之间的关系。

（此处省略图像描述）

每当 $X$ 作为单一产生式出现时，不仅可以替换成它的右部内容，还可以替换成 $Y$ 的非单一字符串。$Z$ 同理。我们将这种替代路径称为单一链（unit chains）。上述图中的所有单一链如下：

\begin{align*} S\to X\to Y \ S\to Y \ S\to Z\to Y \ X\to Y \ Z\to Y \end{align*}

由此可推断出通过单一产生式可达的所有变量。例如，若某规则右部单独出现 $S$，我们可以将其替换为 $S$、$X$、$Y$、$Z$ 的非单一生成结果，因为它们均可通过单一产生式从 $S$ 到达。这些变量构成 $S$ 的单一闭包（unit closure）。该文法的各变量单一闭包为：

\begin{align*} \text{closure}(S) & ={S,X,Y,Z} \ \text{closure}(X) & ={X,Y} \ \text{closure}(Y) & ={Y} \ \text{closure}(Z) & ={Z,Y} \end{align*}

因此，我们将 $X$ 作为单一产生式替换为其闭包内变量的所有非单一生成式，即 $aXb \;|\; ab \;|\; bY \;|\; b$。同理，当 $Z$ 单独出现在规则右部时，也替换为 $Z$ 和 $Y$ 的非单一生成式。将所有单一产生式替换为其对应闭包的非单一效应后，得到：

\begin{align*} S & \to XYZ ;|; XY ;|; XZ ;|; YZ ;|; \mathbf{aXb} ;|; \mathbf{ab} ;|; \mathbf{bY} ;|; \mathbf{b} ;|; \mathbf{ccZ} ;|; \mathbf{cc} \ X & \to aXb ;|; ab ;|; \mathbf{bY} ;|; \mathbf{b} \ Y & \to bY ;|; b \ Z & \to ccZ ;|; cc ;|; bY ;|; b \end{align*}

示例

下面这个文法也包含单一产生式的链条：

\begin{align*} S & \to ACA ;|; CA ;|; AA ;|; AC ;|; A ;|; C \ A & \to aAa ;|; aa ;|; B ;|; C \ B & \to bB ;|; C \ C & \to cC ;|; c \end{align*}

为清晰起见，暂时忽略非单一规则，仅分析单一产生式图中的链结构。

得到各变量的单一闭包如下：

\begin{align*} \text{closure}(S) & = {S,A,B,C} \ \text{closure}(A) & = {A,B,C} \ \text{closure}(B) & = {B,C} \ \text{closure}(C) & = {C} \end{align*}

当这些变量单独作为规则右部的单一产生式出现时，应替换为其闭包中所有变量的非单一生成式。此处可先将 $C$ 的非单一生成式代入 $B$ 的规则，得 $B \to bB \;|\; cC \;|\; c$；再将更新后的 $B$ 代入 $A$，然后将更新后的 $A$ 代入 $S$，最终得到如下文法（适当去除重复项）：

\begin{align*} S & \to ACA ;|; CA ;|; AA ;|; AC ;|; \mathbf{aAa} ;|; \mathbf{aa} ;|; \mathbf{bB} ;|; \mathbf{cC} ;|; \mathbf{c} \ A & \to aAa ;|; aa ;|; \mathbf{bB} ;|; \mathbf{cC} ;|; \mathbf{c} \ B & \to bB ;|; \mathbf{cC} ;|; \mathbf{c} \ C & \to cC ;|; c \end{align*}

重要提示：必须先移除空产生式（λ 规则），再移除单一产生式。

原因如下：考虑以下文法，它原本没有单一产生式，我们尝试先移除 λ：

\begin{align*} S & \to aA \ A & \to BB \ B & \to aBb ;|; \lambda \end{align*}

由于 $B$ 可空，进而 $A$ 也可空。进行替换后：

\begin{align*} S & \to a(A;|;\lambda) \to aA ;|; a \ A & \to BB \to (B;|;\lambda)(B;|;\lambda) \to BB ;|; \mathbf{B} \ B & \to a(B;|;\lambda)b \to aBb ;|; ab \end{align*}

可以看到，移除 λ 后反而引入了新的单一产生式 $A \to B$。

牢记：务必先移除 λ 规则，再处理单一产生式。