前言
这节课我们会检验上下文无关语言类的一些属性，包括它在正则运算下是闭合的，每个正则语言都是上下文无关的，以及一个上下文无关语言和一个正则语言的交集总是上下文无关的。
知识点
正则运算下的闭包
让我们先来证明上下文无关语言在正则运算下是闭合的。
定理9.1. 已知$\Sigma$是一个字母表和$A,B\subseteq \Sigma^{*}$是上下文无关语言。语言$A\cup B,AB$和$A^{*}$都是上下文无关的。
证明：因为$A$和$B$是上下文无关语言，一定存在上下文无关语法
使得$L(G_A)=A$和$L(G_B)=B$。因为由于我们在上下文无关语法中采用的变量名称对它所生成的语言没有影响，假设$V_A$和$V_B$是不相交集不会失去普遍性。
首先让我们为语言$A\cup B$构造一个CFG $G$。这个CFG将会包含所有$G_A$和$G_B$的变量和规则，以及一个新的变量$S$（假设这个变量不包含在$V_A$和$V_B$，并且把它当做$G$的初始变量）和两个新的规则：
正式来说我们可以写成
其中$V=V_A\cup V_B\cup \{S\}$和$R=R_A\cup R_B\cup \{S\rightarrow S_A,S\rightarrow S_B\}$。用典型的方式来写CFG，语法$G$看起来是这样：
明显可以看出$L(G)=A\cup B$；每个推导都是从$S\Rightarrow S_A$或者$S\Rightarrow S_B$开始，然后$S_A$生成的任意$A$中的字符串或者$S_B$生成任意$B$中的字符串。因为语言$A\cup B$是由CFG $G$生成的，所以它是上下文无关的。
接下来我们为语言$AB$构造一个CFG $H$。$H$的构造和上面$G$的类似。CFG $H$将会包含所有$G_A$和$G_B$的变量和规则，以及一个新的初始变量$S$和一个新的规则：
正式来说我们可以写成
其中$V=V_A\cup V_B\cup \{S\}$和$R=R_A\cup R_B\cup \{S\rightarrow S_AS_B\}$。用典型的方式来写CFG，语法$H$看起来像这样：
明显可以看出$L(G)=AB$；每个推导都从$S\Rightarrow S_AS_B$开始，然后$S_A$生成任意$A$中的字符串，$S_B$生成任意$B$中的字符串。因为语言$AB$是由CFG $H$生成的，所以它是上下文无关的。
最后我们来为$A^{*}$构造一个CFG $K$，这次CFG $K$将会只包含$G_A$的变量和规则，以及一个新的初始变量$S$和两个新规则：
正式来说我们可以写成
其中$V=V_A\cup \{S\}$和$R=R_A\cup \{S\rightarrow SS_A,S\rightarrow \varepsilon$。用典型的方式来写CFG，语法$K$看起来像这样：
通过$K$的最左侧推导生成的每个字符串都是从零次或者多次规则$S\rightarrow SS_A$和$S\rightarrow \varepsilon$的应用开始的。这表示每个最左侧推导中都是包含下面的一个序列关系：
等等。在此之后，每个出现的$S_A$都生成任意$A$中的字符串。因此$L(K)=A^{*}$，那么$A^{*}$是上下文无关的。
与正则语言的关系
这部分讨论上下文无关语言和正则语言的关系。特别是我们将证明每个正则语言都是上下文无关的，以及一个上下文无关语言和一个正则语言的交集总是上下文无关的。
让我们从以上事实的第一个开始，也就是每个正则语言都是上下文无关的。我们将会讨论两种不同的方式来证明这个事实。
定理9.2. 已知$\Sigma$是一个字母表，$A\subseteq \Sigma^{*}$是一个正则语言。语言$A$是上下文无关的。
第一个证明：对于每个基于字母表$\Sigma$的正则表达式，通过我们递归使用以下简单的构造可以将它与一个CFG $G$关联起来：
- 如果$R=\varnothing$，那么CFG $G$就是它生成空语言$\varnothing$。
- 如果$R=\varepsilon$，那么CFG $G$就是它生成语言$\{\varepsilon\}$。
- 如果对于每个$a\in \Sigma$有$R=a$，那么CFG $G$就是它生成语言$\{a\}$。
- 如果$R=(R_1\cup R_2)$，那么CFG $G$生成的语言是$L(G_1)\cup L(G_2)$，正如定理9.1证明中所描述的，$G_1$和$G_2$分别与正则表达式$R_1$和$R_2$相关联。
- 如果$R=(R_1R_2)$，那么CFG $G$生成的语言是$L(G_1)L(G_2)$，正如定理9.1证明中所描述的，$G_1$和$G_2$分别与正则表达式$R_1$和$R_2$相关联。
- 如果$R=(R_1^{*})$，那么CFG $G$生成语言$L(G_1)^{*}$，正如定理9.1证明中所描述的，$G_1$与正则表达式$R_1$相关联。
在每种情况下，我们都观察到$L(G)=L(R)$。
现在，假设A是正则的，一定存在一个正则表达式使得$L(R)=A$。由上面所描述通过$R$可以获取到CFG $G$，我们发现$L(G)=A$，因此$A$是上下文无关的。
第二个证明：因为$A$是正则的，一定存在一个DFA
使得$L(M)=A$。
我们将会定义一个CFG $G$，它能有效模拟$M$，生成的字符串恰好能被$M$接受。特别地，我们将会定义
其中变量是$V=\{X_q:q\in Q\}$（一个变量对应$M$中的一个状态）和$R$中包含的一下规则：
- 对于满足$\delta(p,a)=q$的每个选择$p,q\in Q$和$a\in \Sigma$，都有规则包含在$R$中。
- 对于每个状态$q\in F$，都有规则包含在$R$中。
现在，通过检测上述假设的规则，我们发现一个字符串通过$G$的推导都是从初始变量开始，包含了零次或者多次上面第一条规则的使用，然后在采用第二条规则之后接受。在一个变量被消除前总是会出现在每个推导步骤之后。最重要的是最后一步只有一种可能，那就是$X_q$对应着接受状态$q\in F$。通过思考第一种类型的规则，明显可以看出
因此我们得到$X_{q0}\stackrel{*}{\Rightarrow}w$当且仅当存在$q\in F$满足$\delta^{*}(q_0,w)=q$。换个说法就是$L(G)=L(M)$，到此证明就完成了。
正则语言和上下文无关语言的交集
上下文无关语言在某些运算下不是闭合的，但正则语言却是的。比如，上下文无关语言的补集也许不会是上下文无关的，两个上下文无关语言的交集也可能不是上下文无关的。我们在下节课中会来观察这两个事实。
然而有个例外是一个上下文无关语言和一个正则表达式的交集总是上下文无关的，我们马上来证明。这个证明比我们目前为止在本堂课中见到的都要复杂 — 如果你不能完全搞清楚，只要尽力最大的努力去理解背后的思路吧。
定理9.3. 已知$\Sigma$是一个字母表，$A,B\subseteq \Sigma^{*}$是语言，并且假设$A$是上下文无关的，而$B$是正则的。语言$A\cap B$是上下文无关的。
证明：因为语言$A$是上下文无关的，所以一定存在一个$CFG$可以生成它。正如上节课所讨论的，事实上我们可以直接假设存在一个乔姆斯基范式的CFG生成了$A$。有了乔姆斯基范式的CFG，证明就会简单很多了。在这之后我们将会假设
是一个乔姆斯基范式使得$L(G)=A$。因为语言$B$是正则的，一定存在一个DFA
使得$L(M)=B$。
这个证明的主要思想是定义一个新的CFG $H$使得$L(H)=A\cap B$。这个CFG $H$相对于$G$的每个变量都有$|Q|^2$个变量（$H$的变量数量是$G$的$|Q|^2$倍），也许会有点多，但不是什么问题 — 它是一个有限的数量，而且这就是我们所要求的所有变量了。特别地，对于每个变量$X\in V$和每一对$p,q\in Q$，我们都会包含一个变量$X_{p,q}$在$H$中。此外，我们还会加入一个新的初始变量$S_0$到$H$中。
每个变量$X_{p,q}$的意图是它所生成的所有字符串（i）都来自语法$G$中的$X$，并且（ii）造成$M$从状态$p$转移到$q$。完成这些我们还需要针对每条$G$中的规则添加一些规则到$H$中。因为语法$G$被假设为乔姆斯基范式，它的规则只有三种可能的形式，这些规则可以通过以下方式一次一个地处理：
- 对于$G$中形如$X\rightarrow a$的规则，以及每对满足$\delta(p,a)=q$的状态$p,q\in Q$，将规则加入到$H$中。
- 对于$G$中形如$X\rightarrow \Upsilon X$的规则，以及状态$p,q,r\in Q$，将规则加入到$H$中。
- 如果$G$中有$S\rightarrow \epsilon$的规则，并且$q_0\in F$（举例，$\epsilon\in A\cap B$），那么将规则加入到$H$中，$S_0$就是上面提到的$H$的新初始状态。
一旦我们将所有规则添加到$H$中，对于每个接受状态$p\in F$我们还要将规则
添加到$H$中。
$H$中每个变量$X_{p,q}$含义已经在上面解释过了。更正式地来讲，对于每个非空字符串$w\in \Sigma^{*}$，每个变量$X\in V$和每对状态$p,q\in Q$，我们想证明以下等价关系：
这个充要命题可以很自然地分开处理，其中有一个也会很自然地拆成两部分。
首先，我们马上就看出充分命题这个部分
是成立的，因为字符串$w$在$H$中通过$X_{p,q}$的推导可以移除所有下标获得一个$w$在$G$中通过$X$的推导。
接下来我们对$w$长度归纳可以证明充分命题的另外一个部分
也是成立的。基础情况是$|w|=1$（因为我们假设了$w\neq\varepsilon$），在这个情况下我们得到的是对于某个$a\in \Sigma$有$X_{p,q}\Rightarrow_H a$。唯一允许这种推导的规则是上面的第一种，它要求$\delta(p,a)=q$。在普通情况下$|w|\geq 2$，那就一定是
其中变量$\Upsilon_{p,r}$和$Z_{r,q}$满足
而对于字符串$y,z\in\Sigma^{*}$有$w=yz$。由归纳假设我们知道$\delta^{*}(p,y)=r$和$\delta^{*}(r,w)=q$，所以$\delta^{*}(p,w)=q$。
最后我们再对$w$的长度归纳证明
基础情况是$|w|=1$，直接表达就是：如果$X\Rightarrow_G a$和$\delta(p,a)=q$都成立，那么一定有$X_{p,q}\Rightarrow_H a$，因为允许这个推导的规则都包含在了$H$的规则中。在普通情况下$|w|\geq 2$，关系$X\stackrel{*}{\Rightarrow}_G w$说明$X\Rightarrow_G \Upsilon Z$，其中变量$\Upsilon,X\in V$使得$\Upsilon\stackrel{*}{\Rightarrow}_G y$和$Z\stackrel{*}{\Rightarrow}_G z$，而字符串$y,z\in\Sigma^{*}$满足$w=yz$。选择$r\in Q$使得$\delta^{*}(p,y)=r$（因此$\delta^{*}(r,z)=q$），由归纳假设我们知道$\Upsilon_{p,r}\stackrel{*}{\Rightarrow} y$和$Z_{r,q}\stackrel{*}{\Rightarrow} z$，因此$X_{p,q}\Rightarrow_H \Upsilon_{p,r}Z_{r,q}\stackrel{*}{\Rightarrow}_H yz=w$。
因为每个非空字符串的推导都必须从
开始，其中$p\in F$，我们发现$H$所生成的非空字符串$w$明显就是那些由$G$所生成并且满足对于某个$p\in F$有$\delta^{*}(q_0,w)=p$的字符串。等于说，对于$w\neq\varepsilon$的情况有$w\in L(H)\Leftrightarrow w\in A\cap B$。空字符串当做特殊情况来处理，所以接下来我们得到$L(H)=A\cap B$。因此语言$A\cap B$是上下文无关的。
注意9.4. 定理9.3中包含了定理9.2；你可以让$A=\Sigma^{*}$（它是上下文无关的），为$B$选择任意正则语言，然后得到的就是$\Sigma^{*}\cap B = B$是上下文无关的。因为定理9.2的两种证明比我们上面这个看起来简单很多，所以把它们放在前面更好些。
前缀、后缀和子串
让我们在结束本节课之前再来快速过一些例子。回想我们在第6节课中对于任意语言$A\subseteq\Sigma^{*}$我们定义
让我们证明如果$A$是上下文无关的，那么以上三个语言都是上下文无关的。未来了节省时间，我们只会解释如何写出这些语言的上下文无关语法，而且不会详细证明这些语法是正确的。在所有三种情况中我们会假设$G=(V,\Sigma,R,S)$是一个乔姆斯基范式的CFG使得$L(G)=A$。
我们语法$G$的基础上我们还需要一个假设，$G$中的任意变量都不会生成空语言。一个生成空语言的变量，我们称它为无用变量，说服自己无用变量是没用的应该并不难（有一种情况是例外）。然后如果你又任意生成非空语言的乔姆斯基范式CFG，你可以轻松写出一个新的乔姆斯基范式CFG，它不包含任何无用变量，只需要移除无效变量以及出现无效变量的规则。
唯一一种例外情况就是空语言本身，他要求初始变量就是无用的（你将会需要至少一个无效变量来确保语法的规则集合不是空的，而且遵守了乔姆斯基范式的条件）。然而，我们并不需要担心这种情况，因为$Prefix(\varnothing),Suffix(\varnothing),Substring(\varnothing)$都等同于空语言，因此也都是上下文无关的。
对于语言$Prefix(A)$，我们将会设计一个CFG $H$如下。首先，对于每个$G$使用的变量$X\in V$，我们将这个变量包含在$H$中，并且再添加一个变量$X_0$。这个思路是$H$中的$X$所生成的字符串和$G$中的一样，而$X_0$将会生成所有$G$中$X$所生成的字符串的前缀。我们加入$H$中的规则如下：
- 对于$G$中每个形如$X\rightarrow\Upsilon Z$的规则，加入这些规则到$H$中：
- 对于$G$中每个形如$X\rightarrow $的规则，加入这些规则到$H$中：
最后我们使用$S_0$作为$H$的初始变量。
语言$Suffix(A)$的思路和上面类似，对于它我们将会构造一个CFG $K$。这次，对于每个$G$中使用的变量$X\in V$，我们也会把它加入到$K$中，而且也要添加一个变量$X_1$。这个思路是$K$中的$X$所生成的字符串和$G$中的一样，而$X_1$将会生成$G$中所有$X$所生成的字符串的前缀。我们加入$H$中的规则如下：
- 对于$G$中每个形如$X\rightarrow\Upsilon Z$的规则，加入这些规则到$K$中：
- 对于$G$中每个形如$X\rightarrow $的规则，加入这些规则到$H$中：
最后我们使用$S_1$作为$K$的初始变量。
为了获得子串$Substring(A)$的CFG $J$，我们可以简单地关联上述两个构造（先对$G$采用任意一种构造，然后再对得到的CFG采用另一种）。等于说，对于每个$X\in V$我们可以加入变量$X,X_0,X_1,X_2$到$J$中，并且加入如下规则：
- 对于$G$中每个形如$X\rightarrow\Upsilon Z$的规则，加入这些规则到$J$中：
- 对于$G$中每个形如$X\rightarrow $的规则，加入这些规则到$J$中：
最后我们使用$S_2$作为$J$的初始变量。变量$X,X_0,X_1,X_2$的含义分别对应着$G$中$X$所生成的字符串，以及这些字符串的前缀、后缀和字符串。