CFG 的简化

消除无用符号

Definition

对于 CFG $G=(V,T,P,S)$， 称符号 $X\in V\cup T$ 是有用符号当且仅当存在某个形如 $S\stackrel{\ast }{\Rightarrow }\alpha X\beta \stackrel{\ast }{\Rightarrow }w$ 的推导，其中 $w\in T^{\ast },\alpha ,\beta \in (V\cup T{)}^{\ast }$ 称符号 $X$ 是产生符号当且仅当存在 $w\in T^{\ast },X\stackrel{\ast }{\Rightarrow }w$ 称符号 $X$ 是可达符号当且仅当存在 $\alpha ,\beta \in (V\cup T{)}^{\ast },S\stackrel{\ast }{\Rightarrow }\alpha X\beta$

设 $L(G)\ne \varnothing$，$G_1=(V_1,T_1,P_1,S)$ 是通过以下步骤获得的文法：

1. 消除非产生符号，得到 $G_2$
2. 消除非可达符号 则 $G_1$ 中没有无用符号，即 $L(G_1)=L(G)$

• 次序是敏感的

Proof

若 $X$ 是剩余符号之一，因为 $X$ 没有在第二步中被消除，因此 $G_2$ 中存在 $\alpha$ 和 $\beta$ 满足 $S\stackrel{\ast }{\Rightarrow }\alpha X\beta$，由于推导过程中使用的符号都是可达的，因此 $G_1$ 中 $S\stackrel{\ast }{\Rightarrow }\alpha X\beta$ $\alpha X\beta$ 中每个符号都属于 $V_2\cup T_2$，因此它们都是产生的。对于 $G_2$ 中某个 $\alpha X\beta$ 得到的推导，它仅包含从 $S$ 可达的符号，因此这个推导也是 $G_1$ 中的推导。 因此 $G_1$ 中没有无用符号。

消除 $ϵ$ 产生式

称符号 $A\in V$ 是可致空的当且仅当 $A\stackrel{\ast }{\Rightarrow }ϵ$

通过以下步骤可以消除 $G$ 中的 $ϵ$ 产生式，得到 $G_1$：

• 计算 $G$ 的可致空符号集
• 对于每一个产生式 $A\to A_1\dots A_k$，在 $G_1$ 中对应一组产生式，每个可致空符号或出现或不出现（不能出现全不出现的情况）
• 去除 $G$ 中的所有 $ϵ$ 产生式 则 $G_1$ 满足 $L(G_1)=L(G)-\{ϵ\}$

消除单位产生式

形如 $A\to B$ 的产生式称为单位产生式 若 $A\stackrel{\ast }{\Rightarrow }B$，且推导过程中只使用了单位产生式，则称 $(A,B)$ 为单位对

通过以下步骤可以消除 $G$ 中的单位产生式，得到 $G_1$：

• 计算 $G$ 的单位对集合
• 对每个单位对 $(A,B)$，在 $G_1$ 中加入 $A\to \alpha$，其中 $B\to \alpha$ 是一个非单位产生式

CFG 的简化

通过以下步骤对 $G$ 进行简化：

• 消除 $ϵ$ 产生式
• 消除单位产生式
• 消除无用符号 简化步骤是次序敏感的

Chomsky 范式

任何不含 $ϵ$ 的非空 CFL 都存在一个 CFG $G$ 使得其产生式仅包含两种形式：

• $A\to BC$，其中 $B,C$ 为变元
• $A\to a$，其中 $a$ 为终结符 且 $G$ 中不包含无用符号。 这样的文法称为 Chomsky 范式（CNF）

先对 $G$ 进行简化得到 $G_2$，对于 $G_2$：

• 若终结符出现在右侧长度大于 1 的产生式中，则引入新的变元 $A$ 替换产生式中的 $a$，且 $A\to a$
• 将右侧长度大于 2 的产生式转换为只包含 2 个变元（通过引入新的变元） 得到 $G_1$，为 CNF