上下文无关语言和非上下文无关语言.docx
《上下文无关语言和非上下文无关语言.docx》由会员分享，可在线阅读，更多相关《上下文无关语言和非上下文无关语言.docx（16页珍藏版）》请在冰点文库上搜索。
上下文无关语言和非上下文无关语言
8上下文无关语言和非上下文无关语言
8.1上下文无关语言的泵引理
从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。
这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。
然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。
本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。
利用这个性质能够发现许多不是CFL的语言。
正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uvmw被FA接受。
如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。
设CFGG的一个推导出现同一个非终结符的嵌套重复，如下面的形式，
SÞ*vAzÞ*vwAyzÞ*vwxyz
其中，v,w,x,y,zÎå*。
推导过程中，出现了AÞ*wAy，我们可以多次重复这个推导过程，如
SÞ*vAzÞ*vwAyzÞ*vw2Ay2zÞ*vw3Ay3zÞ*...Þ*vwmAymz
又由于AÞ*x，因此所有这类字符串vxz,vwxyz,vw2xy2z,...,vwmxymz都输入语言L（G）。
为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。
同时我们也尽量发现分解得到的5个子串：
v,w,x,y,z，的一些性质。
这类似于我们处理正则语言的泵引理。
在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。
因此我们的讨论可以局限在Chomsky范式（CNF）表示的CFG，显然这类文法得到的推导树都是二叉树，即每个父节点至多有两个子节点。
我们先定义几个与二叉树相关的概念。
路径是一串节点组成的序列，前后节点之间有父子关系；路径的长度是路径包含的节点的个数；二叉树的高度是最长路径的长度。
由于非终结符数目有限，如果推导树足够高，那么存在一个路径，某个非终结符在该路径上出现了两次，即出现了前面提到的嵌套重复现象。
引理8.1任给h>=1，如果二叉树的叶结点个数>2h-1，那么该二叉树的高度>h。
证明：
这是一个数学问题。
我们用数学归纳法证明它的逆反命题：
如果二叉树的高度<=h，那么二叉树的叶节点个数<=2h-1。
1.归纳基础，h=1，此时二叉树只有一个根节点，它也是唯一的叶结点，命题成立。
2.归纳推理，设k>=1时，命题成立。
要证明k+1时，命题也成立。
设二叉树T的高度为k+1，则它的根节点的两个子树（以子节点为跟的二叉树）的叶节点数都<=2k-1，因此T的叶节点数<=2k-1+2k-1=2k。
得证。
定理8.1G=（V,å,S,P）是形式为CNF的CFG，共有p个非终结符，则对每个长度>=2p+1的属于L（G）的字符串，都能找到5个字符串v,w,x,y,z满足下面的条件：
u=vwxyz
|wy|>0
|wxy|<=2p+1
vwmxymzÎL（G）,"m>=0
证明：
根据引理8.1，任何一个生成u的推导树高度>=p+2，即至少存在一个长度>=p+2的路径，不妨设d是其中的一个，显然d的最底部是一个终结符，其上的符号都是非终结符，共有p+1个，而不同的非终结符只有p个，根据鸽笼法则，至少存在一个非终结符A在路径d上出现了至少两次，分别将其中最接近根和最接近叶的标记为A1和A2，设A2生成的字符串是x，A1生成的字符串是wxy。
在wxy之前的字符串记为v，在wxy之后的字符串记为z。
图8-1直观地给出了这5个字符串在推导树上的位置。
由于A1为根的推导树高度<=p+2，因此|wxy|<=2p+1。
由于A1为根的推导树是二叉树，因此出了存在从A1到A2的路径，还存在其他路径，则|wy|>0。
最后，存在如下的嵌套重复，
SÞ*vAzÞ*vwAyzÞ*vwxyz
因此满足第4个条件。
类似有限自动机的泵引理，我们也给出一系列CFG的泵引理。
定理8.1a（CFL的泵引理）语言L是CFL，则存在一个整数n，使得对每个uÎL，|u|>=n，都存在5个字符串v,w,x,y,z，满足下面的条件，
u=vwxyz（8.1）
|wy|>0（8.2）
|wxy|<=n（8.3）
vwmxymzÎL（G）,"m>=0（8.4）
证明：
L是CFL，则存在一个CNF形式的CFG生成L-{L}，它的非终结符个数是p，则令n=2p+1，根据定理8.1直接得到定理8.1a的结论。
类似FA的泵引理（见第5章），本节的泵引理也常常用来证明某个语言不是CFL。
通常采用反证法，即要证明对任给的整数n，都存在一个uÎL，|u|>n，找不到满足上面4个条件的5个字符串。
还有另外的方法说明一个语言不是CFL。
根据第7章，由一个FA加一个辅助存储空间（栈）组成的PDA能够接受一个CFL，如果我们能够说明接受一个语言的抽象机至少需要两个栈，那么就能说明这个语言不是CFL。
比如我们知道接受语言aibi的抽象机只需要一个栈，即用一个栈记住前面的a的个数，然后与后面的b比较。
那么容易想到，仅仅一个栈不能接受语言aibici。
下面我们用泵引理来证明我们的直观判断。
例子8.1语言L={aibici|i>=1}，证明L不是CFL。
分析：
反证法。
假设L是CFL，则存在定理8.1a定义的n，选择u=anbncn，显然|u|>n，设存在5个字符串v,w,x,y,z满足式子（8.1）-（8.4）。
由于|wxy|<=n，因此w,x和y至多包含两种字符，又因为|wy|>0，因此无法满足式子vwmxymzÎL（G）,"m>=0，得到矛盾，得证。
显然这个方法实际上证明了更大的语言L1={uÎ{a,b,c}*|na（u）=nb（u）=nc（u）}是非CFL（选取同样的u）。
例子8.2语言L={ss|sÎ{a,b}*}是非CFL。
分析：
前面我们讨论了语言{ssr|sÎ{a,b}*}是CFL。
例子8.1揭示了一个栈不够用的情况，这个例子则显示了数据结构栈不合适的情况。
显然，如果PDA用到的辅助空间不是栈，而是队列，那么就能够类似接受回文语言那样接受L。
反证法，设L是CFL，则存在n，选择u（n）=anbnanbn，设存在v,w,x,y,z满足式子（8.1）-（8.4），我们来发现其中的矛盾。
类似例子8.1，由于|wxy|<=n，则wxy至多包含上面4组字符串的两组，我们分情况讨论。
1.wxy包含第1组和第2组，则vw0xy0z=aibjanbn,i2.wxy包含第2组和第3组，则vw0xy0z=anbiajbn,i3.wxy包含第3组合第4组，则vw0xy0z=anbnaibj,i其他情况可类似证明。
类似例子8.1，例子8.2可用于证明其他一些语言不是CFL，比如{aibiaibi|i>=0},{aibjaibj|i,j>=0},{scs|sÎ{a,b}*,c是特殊字符}等。
上面证明中如何选择u成为关键，尽管正确的选择可能不止一个，但大多数选择不能导出矛盾。
一旦u选好后，则往往需要分情况讨论。
比如例子8.2，可以分下面7种情况讨论，
1.wy只包含第一组的a
2.wy包含第一组的a和第二组的b
3.wy只包含第二组的b
4.wy包含第二组的b和第三组的a
5.wy只包含第三组的a
6.wy包含第三组的a和第四组的b
7.wy只包含第四组的b
这些情况的讨论中，常常有相似之处，可以互相借用。
最后要选择m的值来导致矛盾，通常有多种值可选择，不过用得最多的是m=0或m=2。
例子8.3语言L={xÎ{a,b,c}*|na（x）分析：
这个例子与例子8.1很像，PDA只有一个栈，可以用来比较a和b的数目，也可以用来比较a和c的数目，但不能同时完成两个比较，因此问题源于栈数目不够。
反证法，设L是CFL，则存在n，令u=anbn+1cn+1，设存在满足式子（8.1）-（8.4）的v,w,x,y,z。
分两种情况讨论：
1.wy中至少含有一个a，则wy不能含有c，因此vw2xy2zÏL；
2.wy中不含a，则vw0xy0zÏL。
两种情况都导致矛盾，得证。
注意，上面的方法还可用于说明语言{aibjck|i例子8.4在5.5节我们说明了程序设计语言C存在不能成为正则语言的特征，在第6章，我们用CFG描述了高级程序设计语言的部分语法，本例我们将说明整个高级程序设计语言，比如C，不是CFL。
分析：
C语言的一个特点是，变量在使用之前必须先声明，这个规则等同于规定字符串具有这样的形式，xcx。
其中，x是标识符，c是两个标识符之间的字符串。
例子8.2已经说明了语言{xcx|xÎ{a,b}*}不是CFL，本例扩大了x的字母表，c变成了字符串，但问题的实质没有改变。
反证法，设L是CFL，则存在n。
选择
u中只有一个空格在int之后，这个句子可能带来编译器的警告，但能够通过编译器并得到可执行程序，即先声明了aa...a，然后两次使用aa...a。
根据泵引理，存在u=vwxyz，|wxy|<=n，分情况讨论xy：
1.wy包含空格，则vw0xy0z不再是合法的C程序；
2.wy不包含空格，wxy只在第一组aa...a，则vw0xy0z将改变生命，后面引用非法，不是合格的C程序；
3.类似讨论其他情况，vw0xy0z都不再是合法C程序。
得到矛盾，得证。
我们还可以借用例子8.2来说明C程序语言不是CFL。
例子8.2说明了{anbmanbm|n,m>=0}不是CFL，C语言中函数调用可以转换成这种形式，比如有两个函数f和g，分别有n和m个参数，每次调用都遵循anbm的形式。
类似FA的泵引理有多种弱形式，本节也给出CFG的泵引理的弱形式，它应用的范围更广，称为Ogden引理。
泵引理给出了字符串的“泵”，w和y，的一些信息，但没有谈及这些子串在u中的位置。
Ogden引理能够明确指示u中某部分包含“泵”，因此提供了比泵引理更丰富的信息，有时能够解决泵引理无法解决的问题。
定理8.2（Ogden引理）L是一个CFL，则存在一个整数n，使得任给uÎL,|u|>=n，给u中>=n个字符做标记，则存在5个字符串v,w,x,y,z满足，
u=vwxyz（8.5）
wy至少包含一个标记字符（8.6）
wxy包含不超过n个标记字符（8.7）
x至少包含一个标记字符（8.8）
vwmxymzÎL（G）,"m>=0（8.9）
证明：
类似泵引理的证明，设接受L-{L}的CNF形式的CFG有p个非终结符，令n=2p+1，设uÎL,|u|>=n，且u上n个字符作了标记，在泵引理的证明中，我们选择最长的路径，它自动满足条件（8.5）和（8.9），为了满足（8.6）-（8.8），我们需要更仔细地选择路径。
从根节点出发，每次我们选择子树的叶节点标记多的子节点，扩充进路径。
如果内部节点的两个子节点对应的子树都带有标记的叶节点，则称为branchpoint。
按照我们的选法，每个新加入路径的节点含有的标记叶节点至少是它的父节点含有的数目的一半。
在这种情况下，可以应用下面的引理来完成证明（类似定理8.1的证明用到了引理8.1）。
引理8.2d是二叉树上的一个路径，r是d上的一个接点，如果r的后代包含<=h个branchpoint，则r为根的树包含<=2h个标记叶节点。
证明：
整个证明很类似引理8.1，对branchpoint的个数使用数学归纳法，且把叶节点的数目改成标记叶节点。
此处是2h而不是2h-1的原因是我们把叶节点排除在branchpoint之外。
如果带标记的叶节点也称为branchpoint，那么本命题中的branchpoint实际上是h+1个。
继续定理8.2的证明，引理8.2说明在我们选择的路径上至少有p+1个branchpoint，由于只有p个不同的非终结符，因此至少有两个branchpoint是相同的非终结符，则我们类似定理证明中v,w,x,y,z的选取，根据branchpoint的定义，上面的（8.6）-（8.8）式显然成立。
值得注意的是，普通的泵引理可以看成Ogden定理的特殊情况，即如果字符串上所有的字符都作标记，就自然得到了泵引理。
例子8.5语言L={aibicj|i,j>=0andj¹i}不是CFL。
分析：
反证法。
假设L是CFL，根据定理8.2，存在n，选择u=anbncn+n!
，我们将前面的n个a作标记，根据定理8.2，存在5个字符串v,w,x,y,z。
满足（8.5）-（8.9）式。
分情况讨论：
1.w或y包含不同的字母，则vw2xy2zÏL（不再是a*b*c*的形式）。
2.由于wy至少含有一个标记字符a，则只可能w=aj,y=bj，当m足够大时，如m=n!
/j+1，vwmxymzÏL。
问题：
例子8.5可以用普通的泵引理来说明吗？
例子8.6语言L={apbqcrds|p=0orq=r=s}不是CFL。
分析：
例子8.1说明了{bqcqdq}不是CFL，似乎预示了L也不是CFL。
本例先说明L满足普通泵引理，因此不能用普通泵引理说明L不是CFL。
设n是任意的正整数，任给uÎL,|u|>=n，设u=apbqcrds，则我们都能找到5个字符串v,w,x,y,z满足式子（8.1）-（8.4）。
如果p=0，则令w=b,v=x=y=L,z=bq-1crds,vwmxymz=bm+q-1crdsÎL；如果p>0，则令w=a,v=x=y=L,z=ap-1bqcrds,vwmxymz=am+p-1brcrdsÎL。
现在我们使用定理8.2，设L是CFL，根据定理8.2存在n，令u=abncndn，除了第一个字符a，其他字符都作标记。
设存在v,w,x,y,z满足（8.5）-（8.9）式，则wy至少包含{b,c,d}中的一个，但不能三个都包含，则vw2xy2z包含一个a，但b,c,d的数目不相等，不属于L。
8.2上下文无关语言的交集和补集
根据定理6.1，CFL在合并、连接和Kleene*运算下保持封闭性。
对于正则语言，保持封闭性的运算还可以增加两个：
交集和补集。
CFL是更复杂的语言，它在交集和补集运算下不一定保持封闭性。
定理8.3存在两个CFLL1和L2，它们的交集L1ÇL2不是CFL。
存在CFLL，它的补集L’不是CFL。
证明：
我们利用例子8.3构造CFL如下，
L1={aibjck|iL2={aibjck|i则L1ÇL2={aibjck|i例子8.3的方法可以证明L1ÇL2不是CFL。
L1和L2是CFL，它们分别可由下面的两个CFG生成。
CFGG1:
S®ABC
A®aAb|L
B®bB|b
C®cC|L
CFGG2:
S®AC
A®aAc|B
B®bB|L
C®cC|c
此处省略CFGG1和G2分别生成语言L1和L2的证明。
现在证明第二个命题，用反正法，由于L1ÇL2=（L1’ÈL2’）’，假设CFLL的补集仍然是CFL，那么L1’和L2’也是CFL，根据合并运算保持CFL的封闭性，（L1’ÈL2’）’也是CFL，即L1ÇL2是CFL，这与前面证明的结论矛盾，因此假设不成立。
例子8.7定理8.3证明第二个命题用的是反证法，而不是构造性证明，它能够证明结论，但不能揭示问题出在什么地方。
分析：
令R={a*b*c*}，则L1’=R’È{aibjck|i>=j}，由于R是正则语言，因此R’也是正则语言，同时也是CFL。
另外，{aibjck|i>=j}={am|m>=0}{ajbj|j>=0}{ck|k>=0}，根据CFL在连接运算下的封闭性，{aibjck}也是CFL。
类似的方法能够说明L2’也是CFL，因此L1’ÈL2’=R’È{aibjck|i>=jori>=k}也是CFL。
而（L1’ÈL2’）’不是CFL。
可见前面两次的补集保持了CFL的性质，最后一个补集失去了CFL的性质。
回想定理3.4，两个正则语言的交集仍然是正则语言，我们在已有的两个FA上构造了接受交集语言的FA，那么为什么PDA无法完成类似的构造呢？
在构造FA时，我们定义了新的状态（p,q），用这个2元组同时跟踪原来FA的状态变化，当p和q都处于接受状态时，新FA就到达了接受状态。
类似地，设接受CFLL1和CFLL2的PDA分别是M1=（Q1,å,G,q1,Z1,A1,d1）和M2=（Q2,å,G,q2,Z2,A2,d2），新的PDA的状态集Q=Q1´Q2，我们还需要跟踪栈的变化情况。
根据7.1节的讨论，我们可以严格地限制栈顶处理的规则，比如只允许压入或弹出操作，而不会影响PDA识别语言的能力，因此M1和M2输入同一个字符a时都只有两种移动，而转移函数则分别有四种可能，
d1（p,a,X）=f|{（p’,X’X）}|{（p’,L）}|{（p’,X’X）,（p’,L）}
d2（q,a,Y）=f|{（q’,Y’Y）}|{（q’,L）}|{（q’,Y’Y）,（q’,L）}
那么如何求d（（p,q）,a,（X,Y））？
d1和d2的组合有16种情况，我们用下面的表讨论d的计算。
d1
d2
f
{（p’,X’X）}
{（p’,L）}
{（p’,X’X）,（p’,L）}
f
f
f
f
f
{（q’,Y’Y）}
f
{（（p’,q’）,（X’,Y’）（X,Y））}
{（（p’,q’）,（L,Y’）（X,Y））}?
?
{（q’,L）}
f
{（（p’,q’）,（X’,L）（X,Y））}?
{（p’,q’）,L}
?
{（q’,Y’Y）,（q’,L）}
f
?
?
?
另一种计算方式是，
d1
d2
f
{（p’,X’X）}
{（p’,L）}
{（p’,X’X）,（p’,L）}
f
f
f
f
f
{（q’,Y’Y）}
f
{（（p’,q’）,（X’X,Y’Y））}
{（（p’,q’）,（L,Y’Y））}?
?
{（q’,L）}
f
{（（p’,q’）,（X’X,L））}?
{（p’,q’）,L}
?
{（q’,Y’Y）,（q’,L）}
f
?
?
?
可见我们无法用一个栈模拟两个栈的变化，比如一个栈要压入，另一个栈要弹出，那么用于模拟的栈应该压入还是弹出？
显然，两个PDA中，其中一个没有栈或栈内容没有变化，则能够构造同时跟踪它们的PDA，因此有下面的定理。
定理8.4L1是CFL，L2是正则语言，则L1ÇL2是CFL。
证明：
用构造法证明。
设接受L1的PDAM1=（Q1,å,G,q1,Z0,A1,d1），接受F2的FAM2=（Q2,å,q2,A2,d2）（注意，此处的FA是没有空转移的确定型FA）。
构造接受L1ÇL2的PDAM=（Q,å,G,q0,Z0,A,d）如下，
Q=Q1´Q2
q0=（q1,q2）
A=A1´A2
d（（p,q）,a,Z）={（（p’,q’）,a）|（p’,a）Îd1（p,a,Z）andd2（q,a）=q’}
（1）
d（（p,q）,L,Z）={（（p’,q）,a）|（p’,a）Îd1（p,L,Z）}
（2）
其中，pÎQ1,qÎQ2,ZÎG,aÎå。
我们看到M的状态跟踪了M1和M2的状态的变化，M的栈跟踪了M1的栈的变化。
为了证明M接受L1ÇL2，我们证明一个更普遍的结论：
字符串y使得M1到达状态p，且栈内容为a，使得M2到达状态q，当且仅当y使得M到达状态（p,q），且栈内容为a。
用数学语言描述如下，
任给n>=0,pÎQ1,qÎQ2,y,zÎå*,aÎG*，那么，（q1,yz,Z1）ÞnM1（p,z,a）且d2*（q2,y）=q，当且仅当，（（q1,q2）,yz,Z1）ÞnM（（p,q）,z,a）。
这里n表示移动的步数，对n使用数学归纳法，我们证明必要性。
1.n=0，（q1,yz,Z1）Þ0M1（p,z,a）且d2*（q2,y）=q，显然y=L,p=q1,a=Z1,q=q2，则得到，
（（q1,q2）,yz,Z1）Þ0M（（q1,q2）,z,a）=（（q1,q2）,yz,Z1），得证。
2.设k>=0,n=k时命题成立，要证明n=k+1时也成立。
设（q1,yz,Z1）Þk+1M1（p,z,a）且d2*（q2,y）=q，考虑M1在k+1步移动中的最后一步，如果是空移动，则
（q1,yz,Z1）ÞkM1（p’,z,b）ÞM1（p,z,a）
根据归纳假设有，（（q1,q2）,yz,Z1）ÞkM（（p’,q）,z,b），根据转移函数
（2）有，
（（p’,q）,z,b）ÞM（（p,q）,z,a），得证。
如果最后一步不是空转移，令y=y’a,aÎå，有
（q1,yz,Z1）ÞkM1（p’,az,b）ÞM1（p,z,a）
设q’=d2*（q2,y’），根据归纳假设有，（（q1,q2）,yz,Z1）ÞkM（（p’,q’）,az,b），再根据转移函数
（1）有，
（（p’,q’）,az,b）ÞM（（p,q）,z,a），得证。
充分性证明省略。
受到定理8.4证明的启发，我们再考虑一下是什么原因导致CFL的补集不一定是CFL。
对于FAM=（Q,å,q0,A,d），我们只要略作修改M’=（Q,å,q0,Q-A,d），则M’接受的语言就是L（M）的补集。
那么类似地，对于PDAM=（Q,å,G,q0,Z0,A,d），同样的修改得到M’=（Q,å,G,q0,Z0,Q-A,d），M’接受的语言是否是L（M）的补集呢？
定理8.3证明了不一定，原因在于PDA的不确定性，比如存在
（q0,x,Z0）Þ*M（p,L,a），
也存在
（q0,x,Z0）Þ*M（q,L,a），
pÎA且qÏA，此时xÎL（M），而按照上面的构造方法，也有xÎL（M’）。
而FA尽管也有非确定型FA，但都能发现等价的确定型FA，因此能够避免这种现象。
那么是不是确定型PDA（DPDA）M接受的语言L的补集，可以通过上面方法构造的PDAM’来接受呢？
答案仍然是否定的，这是因为一个不被M接受的字符
升级会员 