上下文无关文法的性质与运算

泵引理

• 上下文无关语言应满足的一个必要条件
• 可用于判定某些语言不是上下文无关语言

引理

有一个对应于 CNF 的语法分析树，且该树产物为 $w$。若最长的路径长度为 $n$，则 $|w|\le 2^{n-1}$

Proof

基础：$n=1$，显然 归纳：根使用的产生式一定是 $A\to BC$ 形式，以 $B$ 和 $C$ 为根的子树的最大路径长度小于等于 $n-1$，则这两颗子树的产物长度至多为 $2^{n-2}$，因此整棵树的产物长度至多为 $2^{n-1}$

不含 $ϵ$ 的非空 CFL $L$，CFG $G$ 为 CNF，$L=L(G)$，设 $|V|=m,n=2^m$，对于任一长度不小于 $n$ 的字符串 $z$，考察 $z$ 的分析树。 设从根节点开始的一条最长路径标记为 $A_0{A}_1\dots A_k$，若 $k<m$，则 $|z|\le 2^{m-1}<2^m$，但 $|z|\ge n=2^m$，因此该分析树高度至少为 $m+1$，因此 $k\ge m$。 由鸽巢原理，设 $A_i=A_j=A$，其中 $0\le i<j\le k$ 将 $z$ 划分为 $uvwxy$，$w$ 由 $A_j$ 的子树产生，$vwx$ 由 $A_i$ 产生。由于没有单位产生式，$vx\ne ϵ$，因为 $A_i$ 的子树高度不超过 $m+1$ 所以 $vwx$ 的长度不超过 $2^m=n$。

Pumping 特性

对任意的 $i\ge 0,u{v}^{i}w{x}^{i}y\in L$

直观上，产生式需包含

$$\begin{array}{rl}S& \to uAy\\ A& \to vAx\\ A& \to w\end{array}$$

因此会产生递归，第二个产生式可以递归 $i$ 次，得到 $u{v}^{i}w{x}^{i}y$

泵引理

$L$ 是 CFL，则存在正常数 $n$，使得任一长度不小于 $n$ 的字符串 $z\in L,|z|\ge n$，都可以分成 5 部分，$z=uvwxy$ 满足：

• $vx\ne ϵ$
• $|vwx|\le n$
• 对任意 $k\ge 0$，有 $u{v}^{k}w{x}^{k}y\in L$

Proof

若 $L-\{ϵ\}=\varnothing$，成立 否则，设 CFG $G$ 为一个 CNF，取 $n=2^{|V|}$ 即可

可用于证明 $L$ 不是 CFL：

• 考虑任一 $n\ge 1$
• 找到一个满足以下条件的 $z\in L,|z|\ge n$
• $z=uvwxy\wedge vx\ne ϵ\wedge |vwx|\le n$
• 找到一个 $k\ge 0$，使得 $u{v}^{k}w{x}^{k}y\notin L$

Example

$L=\{0^k{1}^k{2}^k|k\ge 1\}$

若是 CFL，设 $n\ge 1$ 为泵引理得到的常数，考虑串 $z=0^n{1}^n{2}^n,z=uvwxy,|vwx|\le n,vx\ne ϵ$ 观察到 $vwx$ 不能同时包含 0 和 2，因为 $|vwx|\le n$ 若 $vwx$ 中没有 2，则 $vx$ 中包含 0 和 1，且至少有其中之一。由泵引理，$uwy$ 应该属于 $L$，但是 $uwy$ 中包含 $n$ 个 2 和不到 $n$ 个的 0 或 1 若 $vwx$ 中没有 0，同理

Example

$L=\{0^i{1}^j{2}^i{3}^j|i\ge 1\wedge j\ge 1\}$

取 $z=0^n{1}^n{2}^n{3}^n=uvwxy$， 若 $vwx$ 含一种符号，则 $uwy$ 至多含三种符号，若 $vwx$ 含两种符号，则 $uwy$ 含两种符号，总有 $uwy\notin L$

Example

$L=\{ww|w\in \{0,1{\}}^{\ast }\}$

取 $z=0^n{1}^n{0}^n{1}^n=uvwxy$，由于 $|vwx|\le n$，则 $|uwy|\ge 3n$ 若 $vwx$ 在前 $n$ 个 0 中，设 $vx$ 包含 $k$ 个 0，则 $uwy$ 以 $0^{n-k}{1}^n$ 开头。$|uwy|=4n-k$，若 $uwy=tt$，则 $|t|=2n-k/2>2n-k$，因此 $t$ 一定在第一段 1 后结束，不能重复。 若 $vwx$ 跨越了第一段 0 和第一段 1，设 $vx$ 中包含 $k_1$ 个 0 和 $k_2$ 个 1，则 $uwy$ 以 $0^{n-k_1}{1}^{n-k_2}$ 开头。$|uwy|=4n-k_1-k_2$ ，若 $uwy=tt$，则 $|t|=2n-(k_1+k_2)/2$ ，矛盾 其余情况类似。

封闭运算

替换

$L$ 为语言的集合，$s:\Sigma \to L$，

$$s(w)=s(a_1{a}_2\dots a_n)=s(a_1)s(a_2)\dots s(a_n)$$ $$s(L)=\bigcup _{w\in L}s(w)$$

若 $L$ 为 $\Sigma$ 上的 CFL，对任何 $a\in \Sigma$，$s(a)$ 为 CFL，则 $s(L)$ 为 CFL。

并

若 $L$ 和 $M$ 为 CFL，则 $L\cup M$ 为 CFL 可用替换证明

交、补、差

• ! CFL 间的交、补、差不一定是 CFL 反例： $L=\{0^n{1}^n{2}^i|n,i>0\}$，$M=\{0^i{1}^n{2}^n|n,i>0\}$ 为 CFL，但 $L\cup M=\{0^n{1}^n{2}^n|n>0\}$ 不为 CFL

与正规语言的交

若 $L$ 为 CFL，$R$ 为正规语言，则 $L\cap R$ 为 CFL 课通过构造 PDA 证明

闭包

若 $L$ 为 CFL，则 $L^{\ast }$ 和 $L^{+}$ 也为 CFL

连接

若 $L$ 和 $M$ 为 CFL，则 $LM$ 为 CFL

反转

若 $L$ 为 CFL，则 $L^R$ 为 CFL

同态

映射 $h:\Sigma \to T^{\ast }$，若 $L$ 为 CFL，则 $h(L)$ 为 CFL

Example

证明 $L=\{a^i{b}^j{c}^k{d}^k|i,j,k\ge 0，若i=1则j=k\}$ 不是 CFL 若是， $L^{\prime }=L\cap L(ab{b}^{\ast }c{c}^{\ast }d{d}^{\ast })=\{a{b}^k{c}^k{d}^k|k\ge 1\}$ 为 CFL，设 $h(a)=ϵ,h(b)=0,h(c)=1,h(d)=2$，则

$$h(L)=\{0^k{1}^k{2}^k|k\ge 1\}$$

为 CFL，矛盾。

逆同态

若 $L$ 为 CFL，则 $h^{-1}(L)$ 为 CFL

CFL 的判定性质

是否为空

• 计算生成符号集
• 判定 $S$ 是否为生成符号 时间复杂度为 $O(n)$

是否包含某串

• 将文法变换为 Chomsky 范式
• 用 CYK 算法进行判定 CYK 算法时间复杂度为 $O(n^3)$

CYK 算法

• $X_{ij}$ 为可以推导出 $a_i{a}_{i+1}\dots a_j$ 的变元的集合
• 从下往上填表处理
• 若 $A\to a_i$ 为产生式，则 $A\in X_{ii}$
• $j>i$ 时，$A\in X_{ij}$ 当且仅当存在 $k,i\le k<j$，有 $B\in X_{ik}$ 和 $C\in X_{(k+1)j}$ 且 $A\to BC$ 为产生式

Example

判定 $L$ 是否生成无限多个串 设 G 中非终结符的数量为 $m$，令 $p=2^m$，枚举所有长度满足 $p\le |w|<2p$ 的串 $w$ 并判定 $w$ 是否属于 $L$，若存在这样的串，则 $L$ 是无限的，否则是有限的。

若找到了这样的 $w$，则根据泵引理，$w=uvxyz$，可以通过重复 $v$ 和 $y$ 来让串的长度无限伸长，$L$ 是无限的。 若 $L$ 是无限的，设 $w$ 为 $L$ 中满足 $|w|\ge p$ 的最短的串，则 $w=uvxyz$ 且 $|vxy|\le p,vy\ne ϵ$，若 $|w|\ge 2p$，则 $uxz\in L$ 且 $p\le |uxy|<|w|$，与 $w$ 为最短的串矛盾。因此总能找到 $p\le |w|<2p$ 的串，从而被算法判定为无限的。