上下文无关文法

上下文无关文法的定义

定义文法 $G = (V, T, P, S)$，其中产生式，除了空产生式外，有如下特点：

$$\forall \alpha \to \beta \in P, \quad \beta \in (V \cup T)^{\ast}, \quad \text{均有 } |\beta| \geq |\alpha|, \text{并且 } \alpha \in V$$

派生树

设有 CFG $ G = (V, T, P, S)$，$G$ 的派生树是满足如
下条件的有序树。

1. 树的每个顶点有一个标记 $X$，且 $X \in V \cup T \cup \{\epsilon\}$；
2. 树根的标记为 $S$；
3. 如果非叶子顶点 $v$ 标记为 $A$，$v$ 的儿子从左到右依次为$v_1, v_2, \dots, v_n$，并且它们分别标记为$X_1, X_2, \dots, X_n$，则 $A \to X_1 X_2 \cdots X_n \in P$；
4. 如果 $X$ 是一个非叶子顶点的标记，则 $X \in V$；
5. 如果顶点 $v$ 标记为 $\epsilon$，则 $v$ 是该树的叶子，并且 $v$ 是其父顶点的惟一儿子。

派生树都是 CFG 的派生树。

顶点的结果

派生树 $T$ 的所有叶子结点从左到右的符号串为 $X_1 X_2 \cdots X_n$是 $T$ 的结果。

CFG 的化简

删除无用符号

无用符号

上下文无关文法的性质

CFL 的泵引理

对于任意的 CFL $L$，存在仅仅依赖于 $L$ 的正整数 $N$，对于任意的 $z \in L$，当 $|z| \geq N$ 时，存在 $u, v, w, x, y$，使得 $z = uvwxy$，同时满足：

1. $|vwx| \leq N$；
2. $|vx| \geq 1$；
3. 对于任意的非负整数 $i$，$u v^i w x^i y \in L$。