«自动机理论、语言和计算导论»笔记：第七章 上下文无关语言的性质
7.1 CFG 的范式
为了得到 CNF 的 CFG，我们需要做一些简化操作。
顺序如下：
-
消空生成式
-
消单生成式
-
消无用符号
7.1.1 消无用符号（非生成、不可达）
如果存在 $S \stackrel{*}{\Rightarrow } \alpha X \beta \stackrel{*}{\Rightarrow } w$ 形式的推导，则 X 是有用的，称X是有用符号。（ $w$ 属于 $T^*$ ）。否则是 无用符号。
设有终结串 $w$，若 $X \stackrel{*}{\Rightarrow } w$ ，则 $X$ 是有生成能力的（generaing），或称 X 是 生成符号。
设有终结串 $\alpha , \beta $，如果 $S \stackrel{*}{\Rightarrow } \alpha X \beta $，则 $X$ 是 可抵达的（reachable），或称 X 是可达符号。
有用符号就是既有生成能力，又可以抵达的符号。
无用产生式就是所有与无用符号有连接的乘积。例如 $S \to a + abB$ ，而 $B$ 是无用符号，则 $abB$ 是无用产生式。
7.1.3 消除可致空符号（$\varepsilon$ 产生式）
$\varepsilon $ 产生式：形如 $A \to \varepsilon $ 的产生式。也叫 $\lambda $ 产生式。
可致空符号：能够最终产生 $\lambda $ 的产生式。
消除可致空符号的步骤如下：
假设有 CFG $G$ :
-
$S \to AB$ -
$A \to aAA \mid \varepsilon $ -
$B \to bBB \mid \varepsilon $
目标：构造 $G_1$ 使得 $L(G_1) = L(G) - {\varepsilon }$
分析：
显然 A，B 是可致空符号。将 $A \to \varepsilon , B \to \varepsilon $ 带入 G 的生成式。对于 AB，有四种组合：两个都是 $\varepsilon $ ， 或只有 A 是 $\varepsilon $ ，或只有 B 是 $\varepsilon $ ，或两个都不是 $\varepsilon $. 都要带入考虑。不妨简记为 00, 01, 10, 11。对于 AA，BB 同理。可以列出下面的表：
| 代入的产生式 | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
$S \to AB$ |
$\varepsilon$ |
B | A | AB |
$A \to aAA $ |
$a$ |
$aA$ |
$aA$ |
$aAA$ |
$B \to bBB $ |
$b$ |
$bB$ |
$bB$ |
$bBB$ |
从而得到：
-
$S \to \varepsilon \mid A\mid B\mid AB$ -
$A\to a\mid aA\mid aAA$ -
$b\to b\mid bB\mid bBB$
我们去除其中的 $S\to \varepsilon$，从而得到 $G_1$：
-
$S \to A\mid B\mid AB$ -
$A\to a\mid aA\mid aAA$ -
$b\to b|bB|bBB$
$G_1$与原文法$G$不再是同一个文法，因此存在且唯一存在的差别是$G_1$不产生$\varepsilon$串。
7.1.4 消除单生成式
形如 $A\to B$ 的生成式称为单变量生成式，简称 单生成式。如果经过 $A$ 的任意次推导，导出 $A', A'', \cdots$，则 $(A, A'),(A,A''),(A',A''),\cdots$ 称为单元偶对。
【例子】设二型文法 $G = (\{S,A,B\}, \{(,),+,*,a\},P,S)$，其中 $P$:
-
$S\to S+A\mid A$ -
$A\to A*B\mid B$ -
$B\to(S)\mid a$
构造无单生成式的文法 $G_1$。
分析：注意到 $S\to A \to B$，所以存在单元偶对：$(S,A), (S,B), (A,B)$
对于 $(A,B)$：$A \to A*B\mid (S)\mid a$
对于 $(S,A)$：$S\to S+A \mid A*B\mid (S)\mid a$
所以 $P_1$ 为：
-
$S\to S+A \mid A*B\mid (S)\mid a$ -
$A \to A*B\mid (S)\mid a$ -
$B\to(S)\mid a$
7.1.5 消除左递归
若有非终结符 $A$，其推导出的句型以 $A$ 为最左符号，则所属的文法是左递归文法。
直接左递归
形如 $A\to A \alpha \mid \beta$ 的句型是直接左递归的。
消除方法：
【例子】现有：$A \to A \alpha _1 \mid A \alpha _2 \mid \beta _1 \mid \beta 2$
第一步：
$A \to \beta _1 A' \mid \beta _2 A'$
第二步：
$A ' \to \varepsilon \mid \alpha _1 A' \mid \alpha _2 A'$
也即，所有 $P \to P \alpha \mid \beta $ 都可以转化为：
$P \to \beta P', P' \to \alpha P' \mid \varepsilon $
间接左递归
需要解一次以上引用的左递归是间接左递归。
例如：
$A \to B\alpha \mid C$ $B \to A\beta \mid D$
移除间接左递归，只需要解引用，使之变成直接左递归。
7.2 CFL 的封闭性
设 $L_1,L_2$ 是二型语言，则 $L_1 \cup L_2, L_1L_2, L_1 ^*$ 是二型语言。
二型语言对交不封闭，对补不封闭，对置换封闭。