上下文无关文法和上下文无关语言

上下文无关文法(CFG, Context-Free Grammar)

CFG为一个四元组：

$G=(V,T,P,S)$

• $V$：非终结符（变量、语法范畴）的有穷集
• $T$：终结符的有穷集
  • 终结符和非终结符不能有重复$V\cap T=\emptyset$
• $P$：产生式的有穷集，产生式可以表示为$A\rightarrow\alpha$，读作“$A$定义为$\alpha$”，其中
  • $A$：产生式的头/左部，$A\in V$
  • $\rightarrow$：产生式符号，表示“定义为”
  • $\alpha$：产生式的体/右部，$\alpha\in (V\cup T)^*$是一个字符串
• $S$：初始符号，$S\in V$

注：

• 多条产生式$A\rightarrow\alpha_1,A\rightarrow\alpha_2,A\rightarrow\alpha_3,\dots$合写为$A\rightarrow\alpha_1|\alpha_2|\alpha_3|\dots$
• 变元$A$的全体产生式称为$A$产生式

规约（由字符串到CFG）和派生（由CFG到字符串）

对于一个CFG$G=(V,T,P,S)$，字符串$\alpha,\beta,\gamma\in(V\cup T)^*$

“可派生”和“可规约”符号$\mathop{\Rightarrow}\limits_{G}$定义

用$A\rightarrow\gamma$的右部替换$\alpha A\beta$中的变元$A$得到$\alpha\gamma\beta$

$\alpha A\beta\mathop{\Rightarrow}\limits_{G}\alpha\gamma\beta\quad:=\quad \begin{aligned} \alpha A\beta\text{可派生出}\alpha\gamma\beta\\ \alpha\gamma\beta\text{可规约为}\alpha A\beta\\ \end{aligned} \quad:=\quad (\exist A\in V)A\rightarrow\gamma\in P$

“$m$步派生”符号$\mathop{\Rightarrow}\limits_{G}^m$定义

$\alpha$经过$m$次派生过程可以得到$\beta$

$\alpha\mathop{\Rightarrow}\limits_{G}^m\beta\quad:=\quad(\exist\alpha_1,\dots\alpha_m\in(V\cup T)^*,\alpha_i\mathop{\Rightarrow}\limits_{G}\alpha_{i+1})\alpha=\alpha_1,\beta=\alpha_m$

“多步派生”符号$\mathop{\Rightarrow}\limits_{G}^*$定义

$\alpha$经过多次派生过程可以得到$\beta$

$\alpha\mathop{\Rightarrow}\limits_{G}^*\beta\quad:=\quad(\exist m\in\mathbb N_+)\alpha\mathop{\Rightarrow}\limits_{G}^m\beta$

若语境中$G$已知，则$G$可省略。$\mathop{\Rightarrow}\limits_{G}$、$\mathop{\Rightarrow}\limits_{G}^m$、$\mathop{\Rightarrow}\limits_{G}^*$可分别省略为$\mathop{\Rightarrow}\limits$、$\mathop{\Rightarrow}\limits^m$、$\mathop{\Rightarrow}\limits^*$。

“最左派生”符号$\mathop{\Rightarrow}\limits_{lm}$定义

只替换字符串最左边的变元

$\alpha A\beta\mathop{\Rightarrow}\limits_{lm}\limits\alpha\gamma\beta\quad:=\quad\alpha A\beta\mathop{\Rightarrow}\limits\alpha\gamma\beta\wedge\alpha\text{中没有变元}$

同理可定义“$m$步最左派生”$\mathop{\Rightarrow}\limits_{lm}^m$和“多步最左派生”$\mathop{\Rightarrow}\limits_{lm}^*$。

“最右派生”符号$\mathop{\Rightarrow}\limits_{rm}$定义

只替换字符串最右边的变元

$\alpha A\beta\mathop{\Rightarrow}\limits_{lm}\limits\alpha\gamma\beta\quad:=\quad\alpha A\beta\mathop{\Rightarrow}\limits\alpha\gamma\beta\wedge\beta\text{中没有变元}$

同理可定义“$m$步最右派生”$\mathop{\Rightarrow}\limits_{rm}^m$和“多步最右派生”$\mathop{\Rightarrow}\limits_{rm}^*$。

任何派生都有等价的最左和最右派生过程

$A\mathop{\Rightarrow}\limits^*w\Leftrightarrow A\mathop{\Rightarrow}\limits_{lm}^*w\Leftrightarrow A\mathop{\Rightarrow}\limits_{rm}^*w$

案例：回文语言$L=\{w\in\{0,1\}^*|w=w^R\}$的CFG

$G=(\{A\},\{0,1\},\{A\rightarrow\varepsilon|0|1|0A0|1A1\},A)$

例如，一个回文串派生过程$A\mathop{\Rightarrow}\limits^70101001001010$可以表示如下：

$\begin{aligned} &A\\ &\Downarrow\text{使用产生式}A\rightarrow 0A0\\ 0&A0\\ &\Downarrow\text{使用产生式}A\rightarrow 1A1\\ 01&A10\\ &\Downarrow\text{使用产生式}A\rightarrow 0A0\\ 010&A010\\ &\Downarrow\text{使用产生式}A\rightarrow 1A1\\ 0101&A1010\\ &\Downarrow\text{使用产生式}A\rightarrow 0A0\\ 01010&A01010\\ &\Downarrow\text{使用产生式}A\rightarrow 0A0\\ 010100&A001010\\ &\Downarrow\text{使用产生式}A\rightarrow 1\\ 010100&1001010\\ \end{aligned}$

上下文无关语言(CFL, Context-Free Language)：上下文无关文法的语言

CFG$G=(V,T,P,S)$的语言定义为：由初始符号派生的所有仅由终结符构成字符串的集合

$\bm L(G)=\{w|w\in T^*,S\mathop{\Rightarrow}\limits_{G}^*w\}$

在上下文无关文法派生的每一步$\alpha A\beta\mathop{\Rightarrow}\limits_{G}\alpha\gamma\beta$，$\gamma$都只与$A$有关而与$\alpha$和$\beta$无关，因此称为“上下文无关”语言。

$\begin{aligned} \alpha\text{是}G\text{的句型}&:=&\alpha\in(V\cup T)^*\wedge S\mathop{\Rightarrow}\limits^*\alpha&\\ \alpha\text{是}G\text{的左句型}&:=&\alpha\in(V\cup T)^*\wedge S\mathop{\Rightarrow}\limits_{lm}^*\alpha&\\ \alpha\text{是}G\text{的右句型}&:=&\alpha\in(V\cup T)^*\wedge S\mathop{\Rightarrow}\limits_{rm}^*\alpha&\\ \alpha\text{是}G\text{的句子}&:=&\alpha\in T^*\wedge S\mathop{\Rightarrow}\limits^*\alpha&\\ \end{aligned}$

以下3个案例来自于《正则语言》一节，它们都不是正则语言，但是是上下文无关语言。

上下文无关语言的封闭性

代换

代换是一个字母表$\Sigma$上的字符串到另一个字母表$\Gamma$上的语言$\Gamma^*$的函数$s:\Sigma^*\rightarrow 2^{\Gamma^*}$。递归定义：

$\begin{aligned} s(\varepsilon)&=\{\varepsilon\}&& &\text{空串的代换}&\\ s(a)&=L_a&&(a\in\Sigma,L_a\in 2^{\Gamma^*})&\text{字符的代换}&\\ s(xa)&=s(x)s(a)&&(x\in\Sigma^*)&\text{字符串的代换}&\\ s(L)&=\bigcup_{x\in L}s(x)&& &\text{语言的代换} \end{aligned}$

代换的封闭性(未完成)

对于字母表$\Sigma$上的一个CFL$L\in\Sigma^*$，那么对于代换$s$有如下定理：

$(\forall a\in\Sigma)s(a)\text{是CFL}\Rightarrow s(L)\text{是CFL}$

证明：

设：

• CFL$L$的CFG是$G=(V,T,P,S)$，即$L=\bm L(G)$；
• $s(a)$的CFG是$G_a=(V_a,T_a,P_a,S_a)$，即$s(a)=\bm L(G_a)$。

那么构造一个CFG$G'$：

$G'=(V',T',P',S)$

其中：

• $V'=V\cup(\bigcup_{a\in T}V_a)$，变元是原CFL和所有代换CFL的变元并集
• $T'=\bigcup_{a\in T}T_a$，终结符中只包含代换CFL的终结符，不包含原CFL的终结符
• $P'$中包含$\bigcup_{a\in T}P_a$和$P$，但要将$P$中产生式的每个终结符$a$替换为对应的代换文法$G_a$的开始符号$S_a$。

案例

案例：语言$L=\sum_{n=0}^\infty\bm 0^n\bm 1^n=\{0^n1^n|n\geq 0\}$的CFG

$G=(\{S\},\{0,1\},\{S\rightarrow\varepsilon|0S1\},S)$

案例：语言$L=\{w|w\text{由数量相等的01构成}\}$的CFG

$G=(\{S\},\{0,1\},\{S\rightarrow\varepsilon|S0S1S|S1S0S\},S)$

案例：语言$L=\{0^i1^j|i>j\}$的CFG

$G=(\{S,A,B\},\{0,1\},\{S\rightarrow AB,A\rightarrow A0|0,B\rightarrow\varepsilon|0B1\},S)$

经典案例：四则运算表达式的CFG

表示一个由加减乘除和括号以及二进制数表示的四则运算CFG

$G=\{\{E,I\},\{0,1,+,-,\times,\div,(,)\},P,E\}$

其中，产生式的有穷集$P$为：

$P=\left\{ \begin{aligned} E&\rightarrow E+E|E-E\\ E&\rightarrow E\times E|E\div E\\ E&\rightarrow (E)|I\\ I&\rightarrow 0|1|I0|I1\\ \end{aligned} \right\}$

乔姆斯基范式(Chomsky Normal Form, CNF)

如果一个上下文无关文法$G=(V,T,P,S)$的每一个产生式都具有如下形式：

$\begin{aligned} A&\rightarrow BC&&(A,B,C\in V\wedge B,C\not =S)&\\ A&\rightarrow a&&(A\in V\wedge a\in T)&\\ \end{aligned}$

那么称此上下文无关文法为乔姆斯基范式。

可以证明任何上下文无关文法都可以转化为乔姆斯基范式，其证明过程也是将任意上下文无关文法转化为乔姆斯基范式的方法，比较简单，此处略。

乔姆斯基范式的性质

• 派生出长度为$n$的串恰好需要$2n-1$步
  • 其中$n-1$步产生一个由变元组成的长度为$n$的串
  • 其中$n$步将长度为$n$的变元串派生为终结符串
• 存在多项式时间算法判断任意字符串是否在给定的乔姆斯基范式
  • 编译原理中常见的CYK算法即是以CNF为基础

格雷巴赫范式(Greibach Normal Form, GNF)

如果一个上下文无关文法$G=(V,T,P,S)$不含空串$\varepsilon\not\in T$，且每一个产生式都具有如下形式：

$A\rightarrow a\alpha\quad(a\in T\wedge\alpha\in(V\cup T\cup\{\varepsilon\})^*)\\$

那么称此上下文无关文法为格雷巴赫范式。

可以证明任何不含空串$\varepsilon\not\in T$的上下文无关文法都可以转化为格雷巴赫范式，其证明过程也是将任意上下文无关文法转化为格雷巴赫范式的方法，比较简单，此处略。

乔姆斯基范式的性质

• 派生出长度为$n$的串恰好需要$n$步
• 每个产生式引入一个终结符

上下文无关语言的泵引理

非上下文无关语言

“上下文有关语言”