上下文无关语言和非上下文无关语言.doc

资源描述

《上下文无关语言和非上下文无关语言.doc》由会员分享，可在线阅读，更多相关《上下文无关语言和非上下文无关语言.doc（10页珍藏版）》请在三一文库上搜索。

1、语言与计算理论导引上下文无关语言与非上下文无关语言8 上下文无关语言和非上下文无关语言8.1 上下文无关语言的泵引理从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。利用这个性质能够发现许多不是CFL的语言。正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是

2、回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m=0，uvmw被FA接受。如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式，S*vAz*vwAyz*vwxyz其中，v, w, x, y, z*。推导过程中，出现了A*wAy，我们可以多次重复这个推导过程，如S*vAz*vwAyz*vw2Ay2z*vw3Ay3z*.*vwmAymz又由于A*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ., vwmxymz都输入语言L(

3、G)。为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。这类似于我们处理正则语言的泵引理。在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。因此我们的讨论可以局限在Chomsky范式（CNF）表示的CFG，显然这类文法得到的推导树都是二叉树，即每个父节点至多有两个子节点。我们先定义几个与二叉树相关的概念。路径是一串节点组成的

4、序列，前后节点之间有父子关系；路径的长度是路径包含的节点的个数；二叉树的高度是最长路径的长度。由于非终结符数目有限，如果推导树足够高，那么存在一个路径，某个非终结符在该路径上出现了两次，即出现了前面提到的嵌套重复现象。引理8.1 任给h=1，如果二叉树的叶结点个数2h-1，那么该二叉树的高度h。证明：这是一个数学问题。我们用数学归纳法证明它的逆反命题：如果二叉树的高度=h，那么二叉树的叶节点个数=1时，命题成立。要证明k+1时，命题也成立。设二叉树T的高度为k+1，则它的根节点的两个子树（以子节点为跟的二叉树）的叶节点数都=2k-1，因此T的叶节点数=2p+1的属于L(G)的字符串，都能找到5

5、个字符串v, w, x, y, z满足下面的条件：u=vwxyz|wy|0|wxy|=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，因此

6、|wxy|0。最后，存在如下的嵌套重复，S*vAz*vwAyz*vwxyz因此满足第4个条件。类似有限自动机的泵引理，我们也给出一系列CFG的泵引理。定理8.1a （CFL的泵引理）语言L是CFL，则存在一个整数n，使得对每个uL，|u|=n，都存在5个字符串v, w, x, y, z，满足下面的条件，u=vwxyz(8.1)|wy|0(8.2)|wxy|=0(8.4)证明：L是CFL，则存在一个CNF形式的CFG生成L-L，它的非终结符个数是p，则令n=2p+1，根据定理8.1直接得到定理8.1a的结论。类似FA的泵引理（见第5章），本节的泵引理也常常用来证明某个语言不是CFL。通常采用反证

7、法，即要证明对任给的整数n，都存在一个uL，|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，

9、，设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, in, jn，显然vw0xy0zL，矛盾；2. wxy包含第2组和第3组，则vw0xy0z=anbiajbn, in, jn，显然vw0xy0zL，矛盾；3. wxy包含第3组合第4组，则vw0xy0z=anbnaibj, in, j=0, aibjaibj | i,j=0, scs | sa,

10、 b*, c是特殊字符等。上面证明中如何选择u成为关键，尽管正确的选择可能不止一个，但大多数选择不能导出矛盾。一旦u选好后，则往往需要分情况讨论。比如例子8.2，可以分下面7种情况讨论，1. wy只包含第一组的a2. wy包含第一组的a和第二组的b3. wy只包含第二组的b4. wy包含第二组的b和第三组的a5. wy只包含第三组的a6. wy包含第三组的a和第四组的b7. wy只包含第四组的b这些情况的讨论中，常常有相似之处，可以互相借用。最后要选择m的值来导致矛盾，通常有多种值可选择，不过用得最多的是m=0或m=2。例子8.3 语言L=xa, b, c* | na(x)nb(x) and

11、na(x)nc(x)不是CFL。分析：这个例子与例子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，因此vw2xy2zL；2. wy中不含a，则vw0xy0zL。两种情况都导致矛盾，得证。注意，上面的方法还可用于说明语言aibjck | ij and ik不是CFL。例子8.4 在5.5节我们说明了程序设计语言C存在不能成为正

12、则语言的特征，在第6章，我们用CFG描述了高级程序设计语言的部分语法，本例我们将说明整个高级程序设计语言，比如C，不是CFL。分析：C语言的一个特点是，变量在使用之前必须先声明，这个规则等同于规定字符串具有这样的形式，xcx。其中，x是标识符，c是两个标识符之间的字符串。例子8.2已经说明了语言xcx | xa, b*不是CFL，本例扩大了x的字母表，c变成了字符串，但问题的实质没有改变。反证法，设L是CFL，则存在n。选择u中只有一个空格在int之后，这个句子可能带来编译器的警告，但能够通过编译器并得到可执行程序，即先声明了aa.a，然后两次使用aa.a。根据泵引理，存在u=vwxyz，|w

13、xy|=0不是CFL，C语言中函数调用可以转换成这种形式，比如有两个函数f和g，分别有n和m个参数，每次调用都遵循anbm的形式。类似FA的泵引理有多种弱形式，本节也给出CFG的泵引理的弱形式，它应用的范围更广，称为Ogden引理。泵引理给出了字符串的“泵”，w和y，的一些信息，但没有谈及这些子串在u中的位置。Ogden引理能够明确指示u中某部分包含“泵”，因此提供了比泵引理更丰富的信息，有时能够解决泵引理无法解决的问题。定理8.2 （Ogden引理）L是一个CFL，则存在一个整数n，使得任给uL, |u|=n，给u中=n个字符做标记，则存在5个字符串v, w, x, y, z满足，u=vwx

14、yz(8.5)wy至少包含一个标记字符(8.6)wxy包含不超过n个标记字符(8.7)x至少包含一个标记字符(8.8)vwmxymzL(G), m=0(8.9)证明：类似泵引理的证明，设接受L-L的CNF形式的CFG有p个非终结符，令n=2p+1，设uL, |u|=n，且u上n个字符作了标记，在泵引理的证明中，我们选择最长的路径，它自动满足条件(8.5)和(8.9)，为了满足(8.6)-(8.8)，我们需要更仔细地选择路径。从根节点出发，每次我们选择子树的叶节点标记多的子节点，扩充进路径。如果内部节点的两个子节点对应的子树都带有标记的叶节点，则称为branch point。按照我们的选法，每个

15、新加入路径的节点含有的标记叶节点至少是它的父节点含有的数目的一半。在这种情况下，可以应用下面的引理来完成证明（类似定理8.1的证明用到了引理8.1）。引理8.2 d是二叉树上的一个路径，r是d上的一个接点，如果r的后代包含=h个branch point，则r为根的树包含=0 and ji不是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包含不同的字母，则vw2xy2zL（不再是a*b*c*的形式）。2. 由于wy至

16、少含有一个标记字符a，则只可能w=aj, y=bj，当m足够大时，如m=n!/j+1，vwmxymzL。问题：例子8.5可以用普通的泵引理来说明吗？例子8.6 语言L=apbqcrds | p=0 or q=r=s不是CFL。分析：例子8.1说明了bqcqdq不是CFL，似乎预示了L也不是CFL。本例先说明L满足普通泵引理，因此不能用普通泵引理说明L不是CFL。设n是任意的正整数，任给uL, |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=

17、bm+q-1crdsL；如果p0，则令w=a, v=x=y=L, z=ap-1bqcrds, vwmxymz=am+p-1brcrdsL。现在我们使用定理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*运算下保持封闭性。对于正则语言，保持封闭性的运算还可以增加两个：交集和补

19、i=k也是CFL。而(L1L2)不是CFL。可见前面两次的补集保持了CFL的性质，最后一个补集失去了CFL的性质。回想定理3.4，两个正则语言的交集仍然是正则语言，我们在已有的两个FA上构造了接受交集语言的FA，那么为什么PDA无法完成类似的构造呢？在构造FA时，我们定义了新的状态(p, q)，用这个2元组同时跟踪原来FA的状态变化，当p和q都处于接受状态时，新FA就到达了接受状态。类似地，设接受CFL L1和CFL L2的PDA分别是M1=(Q1, , G, q1, Z1, A1, d1)和M2=( Q2, , G, q2, Z2, A2, d2)，新的PDA的状态集Q=Q1Q2，我们还需要

20、跟踪栈的变化情况。根据7.1节的讨论，我们可以严格地限制栈顶处理的规则，比如只允许压入或弹出操作，而不会影响PDA识别语言的能力，因此M1和M2输入同一个字符a时都只有两种移动，而转移函数则分别有四种可能，d1(p, a, X)=f | (p, XX) | (p, L) | (p, XX), (p, L)d2(q, a, Y)=f | (q, YY) | (q, L) | (q, YY), (q, L)那么如何求d(p,q), a, (X,Y)？d1和d2的组合有16种情况，我们用下面的表讨论d的计算。d1d2f(p, XX)(p, L)(p, XX), (p, L)fffff(q, YY)f

21、(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, YY), (q, L)f?另一种计算方式是，d1d2f(p, XX)(p, L)(p, XX), (p, L)fffff(q, YY)f(p, q), (XX, YY)(p, q), (L, YY)?(q, L)f(p, q), (XX, L)?(p, q), L?(q, YY), (q, L)f?可见我们无法用一个栈模拟两个栈的变化，比如一个栈要压入，另一个栈要弹出，那么用于模拟的栈应该压入还是弹出？显然，两个PDA中，其中一个

22、没有栈或栈内容没有变化，则能够构造同时跟踪它们的PDA，因此有下面的定理。定理8.4 L1是CFL，L2是正则语言，则L1L2是CFL。证明：用构造法证明。设接受L1的PDA M1=(Q1, , G, q1, Z0, A1, d1)，接受F2的FA M2=(Q2, , q2, A2, d2)（注意，此处的FA是没有空转移的确定型FA）。构造接受L1L2的PDA M=(Q, , G, q0, Z0, A, d)如下，Q=Q1Q2q0=(q1, q2)A=A1A2d(p, q), a, Z)=(p, q), a) | (p, a)d1(p, a, Z) and d2(q, a)=q(1)d(p,

23、q), L, Z)=(p, q), a) | (p, a)d1(p, L, Z)(2)其中，pQ1, qQ2, ZG, a。我们看到M的状态跟踪了M1和M2的状态的变化，M的栈跟踪了M1的栈的变化。为了证明M接受L1L2，我们证明一个更普遍的结论：字符串y使得M1到达状态p，且栈内容为a，使得M2到达状态q，当且仅当y使得M到达状态(p, q)，且栈内容为a。用数学语言描述如下，任给n=0, pQ1, qQ2, y,z*, aG*，那么，(q1, yz, Z1)nM1(p, z, a)且d2*(q2, y)=q，当且仅当，(q1,q2), yz, Z1)nM(p,q), z, a)。这里n表示

24、移动的步数，对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,

25、q2), yz, Z1)kM(p, q), z, b)，根据转移函数(2)有，(p, q), z, b)M(p, q), z, a)，得证。如果最后一步不是空转移，令y=ya, 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。对于FA M=(Q, , q0, A, d)，

26、我们只要略作修改M=( Q, , q0, Q-A, d)，则M接受的语言就是L(M)的补集。那么类似地，对于PDA M=(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)，pA且qA，此时xL(M)，而按照上面的构造方法，也有xL(M)。而FA尽管也有非确定型FA，但都能发现等价的确定型FA，因此能够避免这种现象。那么是不是确定型PDA（DP

27、DA） M接受的语言L的补集，可以通过上面方法构造的PDA M来接受呢？答案仍然是否定的，这是因为一个不被M接受的字符串x可能导致M出现无限移动，那么x同样导致M出现无限移动，因此也不能被M接受（FA上不可能出现无限转移的情况）。利用练习7.27的结论可以解决DPDA无限移动的问题，因此可以构造接受补集的DPDA。这说明了确定型上下文无关语言（DCFL）的补集也是DCFL，特别地，如果一个CFL的补集不是CFL，则该CFL不是DCFL（定理8.3和例子8.7）。8.3 与上下文无关语言相关的判定问题在第5章最后部分，我们考察了许多涉及正则语言的判定问题，其中第一个问题就是成元资格问题，这些问题

28、可以类似地放到CFL上。我们将发现，有些问题可以用相似的方法解决，有些问题涉及到CFL内在不确定性带来的差异，需要寻找新方法，还有些问题，可能没有办法解决，这需要用到更复杂的计算模型来证明。对于CFL基本的乘员资格问题，即任给一个PDA M和字符串x，M是否接受x，原来得简单的方法：将x放入M运行，不再是可行的办法。8.2节我们已经提到，由于PDA的非确定性，一个不被接受的字符串可能导致M无限移动，尽管可能存在某个移动到达拒绝状态，但仍然要等待其他移动结束后，才能判断x是否属于L(M)。我们可以在DPDA上解决这个问题，另外我们从CFG的角度讨论，借助第6章的结论，如果一个CFG没有空产生式和

29、单一产生式，则生成长度为n的字符串的推导步骤至多2n-1步。而对每个PDA都能构造出对应的CFG，因此可以通过CFG来解决这个问题。成员资格问题的判定算法（给定一个PDA M和字符串x，M是否接受x？）定理7.4给出了从PDA M构造CFG G的算法，且L(G)=L(M)。如果待判定的字符串x=L，则用FindNull算法（见6.6节）确定G的起始非终结符是否是可空非终结符；否则利用算法6.1和算法6.2去掉G中的空产生式和单一产生式，得到新文法G，然后用G完成从1步到2|x|-1步的所有推导，如果发现其中一个推导生成了x，则xL(M)，否则xL(M)。我们考察对应第5章问题1和问题2的两个与

30、CFL相关的问题：1. 给定一个CFG G，L(G)=f?2. 给定一个CFG G，L(G)是否是有限集？定理8.1提供了回答这两个问题的方法。首先将G转换成CNF形式的CFG G，设p是G的非终结符的个数，令n=2p+1。如果G能够生成某个字符串，则它一定能够生成某个长度=1，一个叶节点2-h-1的二叉树的高度h。定理8.1 CFG G是一个具有Chomsky范型的上下文无关文法，共有p个变量，任何一个uL(G)且|u|=2-p+1，可以写成u=vwxyz，满足：1）|wy|02）|wxy|=0，vw-mxy-mzL(G)证明：存在一个长度p的路径，因此存在S*vAz*vwAyz*vwxyz

31、。定理8.1a（上下文无关语言的泵引理）L是一个CFL，则存在n，对于所有的uL且|u|=n，则有：u=vwxyz|wy|0|wxy|=0，vw-mxy-mzL。类似正规语言的泵引理，可用于证明某个语言不是CFL，往往需要多个栈的语言（CFL仅需要一个栈）。定理8.2（Ogden引理）L是上下文无关语言，则存在整数n，任给uL且|u|=n，标记u中n个或更多的位置为区别位置，则存在v, w, x, y, z满足：u=vwxyzwy包含至少一个区别位置wxy包含不多过n个区别位置x包含至少一个区别位置任给m=0，vw-mxy-mzL证明：branch point的定义8.2 上下文无关语言的交集

32、和补集定理8.3 两个CFL的交集不一定是CFL，CFL的补集不一定是CFL。定理8.4 CFL和正规语言的交集是CFL。证明：构造法。补集不是CFL的主要原因是非确定型PDA的存在，DPDA的补集是CFL。8.3 与CFL有关的判定问题的解决给定一个PDA M和字符串x，判定x是否被M接受？从一步推导开始检查，直到长度为2|x|-1的推导，如果没有x的推导，则xL(M)，否则xL(M)。给定一个CFG G，判定L(G)是否为空？给定一个CFG G，判定L(G)是否是有限集？首先，测试L是否属于L(G)，如果是则L(G)不空。构造G的Chomsky范型G，p是G的变量数，n=2-p+1，测试从1到n的所有字符串，如果没有字符串属于L(G)，且LL(G)，则L(G)=L(G)=f，再测试n=i2n的所有字符串，如果没有字符串属于L(G)，则L(G)是有限集，否则是无限集。CFL在交集运算下不封闭，并不是说判定一个字符串同时属于两个CFL的问题是不可解的（unsolvable），在第十二章我们将讨论它确实是不可解的。10陶晓鹏 Copyright 2003

展开阅读全文