上下文无关语言的性质.ppt

《上下文无关语言的性质.ppt》由会员分享，可在线阅读，更多相关《上下文无关语言的性质.ppt（30页珍藏版）》请在三一办公上搜索。

1、1,形式语言与自动机,第8章 上下文无关语言的性质,2,主要内容,CFL 的泵引理及其应用CFL 的封闭性封闭运算：并、乘、闭包不封闭运算：交、补CFL 的判定算法。判定 CFG 产生的语言是否为空、有穷、无穷。一个给定的符号串是否为该文法产生的语言的一个句子等问题。,3,8.1 上下文无关语言的泵引理,回顾RG G=(V,T,P,S)，使得 L(G)=L，当 x 足够长时，如|x|V|+1 时，存在 u,v,wT*，|v|1，使得 x=uvw，当 G 为右线性文法时，必定存在语法变量 A，使得如下派生成立：S*uA*uvA*uviA*uviw v 是可以被重复任意多次的字串！,CFL 也有类

2、似性质？,4,上下文无关语言的泵引理,CFL 的自嵌套特性如果 L 是一个 CFL，CFG G=(V,T,P,S)是产生 L 的文法。当L一个无穷语言时，必存在zL，AV，,(VT)*，且 和 中至少有一个不为，使得如下派生成立S*A+A+z即在文法 G 中，存在有如下形式的派生A+A设*v，*x，*u，A*w，*y 可以得到如下派生 S*A*uA*uAy*un An y*uvnAxny*uvnwxny,5,上下文无关语言的泵引理,引理 8-1（CFL的泵引理）对于任意的 CFL L，存在仅仅依赖于 L 的正整数 N，对于任意的 zL，当|z|N时，存在 u,v,w,x,y，使得 z=uvwx

3、y，同时满足：(1)|vwx|N；(2)|vx|1；(3)对于任意的非负整数 i，uviwxiyL。,6,上下文无关语言的泵引理,用 CNF 作为 CFL 的描述工具。对于任意的 zL，当 k 是 z 的语法树的最大路长时，必有|z|2k-1 成立。仅当 z 的语法树呈上图所示的满二元树时，才有|z|=2k-1，其他时候均有|z|2k-1。,7,上下文无关语言的泵引理,取 N=2|V|=2|V|+1-1，zL，|z|N。取 z 的语法树中的最长的一条路 p，p 中的非叶子结点中必定有不同的结点标有相同的语法变量。p 中最接近叶子且都标有相同的语法变量 A 的两个结点为v1,v2。,u,v,w,

4、x,y,8,上下文无关语言的泵引理,z=uvwxy注意到 v1-子树的最大路长小于等于|V|+1，所以，v1 的结果 vwx 满足：|vwx|2(|V|+1)-1=2|V|=Nv1 的后代 v2 标记为变量 A，所以，|vx|1。此时有S*uAy+uvAxy+uvwxy显然，对于 i=0,1,2,3,A*viAxi+viwxi 所以S*uAy+uviAxiy+uviwxiy。,u,v,w,x,y,9,例8-1 证明 L=anbncn|n1不是 CFL。,取 z=aNbNcNL，设 z=uvwxy，主意到|vwx|N，所以 v,w 和 x 并在一起不能同时有 3 种字符。即 v 和 x 不能同时

5、分别为 a 和 c 组成的串，也不可以取它们为形如 ahbf 的串。其他情况的讨论：(1)v=ah，x=bf，h+f 1。uviwxiy=aN+(i-1)hbN+(i-1)fcN，当 i1 时，N+(i-1)hN 和 N+(i-1)fN 中至少有一个成立。uviwxiy=aN+(i-1)hbN+(i-1)fcNL。(2)v=bh，x=cf，h+f 1。uviwxiy=aNbN+(i-1)h cN+(i-1)f当 i1 时，N+(i-1)hN 和 N+(i-1)f N 中至少有一个成立。uviwxiy=aNhbN+(i-1)cN+(i-1)f L。这些都与泵引理矛盾，所以，L 不是 CFL。,1

6、0,例8-1 证明 L=anbncn|n1不是 CFL。,取 z=aNbNcNL，设 z=uvwxy，主意到|vwx|N，所以 v,w 和 x 并在一起不能同时有 3 种字符。可能出现以下几种情况：(1)v 和 x 只包含 a，取 i=2，则在 uv2wx2y 中，a 的个数明显大于 b,c 的个数，因此它不在 L 中。(2)v 和 x 只包含 b 或只包含 c，理由与(1)同，uv2wx2y 也不在 L 中。(3)v 只包含 a,x 只包含 b，取 i=2，则在 uv2wx2y 中，a,b 的个数将超过 c 的个数，它不在 L 中。(4)v 只包含 b,x 只包含c，理由与(3)同，uv2w

7、x2y 也不在 L 中。(5)v 或 x 包含两种不同的符号，例如，v 包含 a 和 b，则在 uv2wx2y 中将呈现 a 和 b 交错出现的情况，显然它不在 L 中。所以，L 不是 CFL。,11,例8-2,证明 L=anbmcndm|n,m1 不是 CFL。取 z=aNbNcNdN，只需讨论如下情况：v=ah,x=bf；v=bh,x=cf；v=ch,x=df，h+f 1 等 3 种情况。设 v=ah,x=bf，并且 h+f 1uviwxiy=aN+(i-1)hbN+(i-1)fcNdN当 i1 时，N+(i-1)h N 和 N+(i-1)f N 至少有一个成立。uviwxiy=aN+(i

8、-1)hbN+(i-1)fcNdNL 同理可以证明，当 v=bh,x=cf 或者 v=ch,x=df，h+f1时，uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL对 i1 成立。由泵引理，L 不是 CFL。,12,8.2 CFL的封闭性,主要讨论：CFL 在并、乘积、闭包、补、交等运算下的封闭性。,13,定理 8-1,定理 8-1 CFL 在并、乘积、闭包运算下是封闭的。令 CFG G1=(V1,T1,P1,S1),L(G1)=L1，G2=(V2,T2,P2,S2),L(G2)=L2，其中V1V2=，且S3,S4,S5V1V2。G3=(V1V2S3,T1T2,P1P2 S3 S1

9、|S2,S3)G4=(V1V2S4,T1T2,P1P2 S4 S1S2,S4)G5=(V1S5,T1,P1 S5 S1S5|,S5)显然，G3,G4,G5 都是 CFG，并且L(G3)=L1L2L(G4)=L1L2L(G5)=L1*,14,定理 8-2,定理 8-2 CFL 在交运算下不封闭的。注意：0n1n2n|n1 不是 CFL。设 L1=0n1n2m|n,m1，L2=0n1m2m|n,m1。G1：S1ABA0A1|01B2B|2 G2：SABA0A|0B1B2|12显然，L(G1)=L1、L(G2)=L2。L=L1L2=0n1n2n|n1 不是 CFL。所以，CFL 在交运算下是不封闭的

10、。,15,推论8-1,推论8-1 CFL在补运算下是不封闭的。由于 CFL 对并运算的封闭性、对交运算的不封闭性和下列式子，可以得出 CF L对补运算是不封闭的结论。,16,定理8-3,定理8-3 CFL 与 RL 的交是 CFL。,M 使用的栈就是 M1 的栈。M 的状态包括两个分量：一个为 M1 的状态，用来使 M 的动作能准确地模拟 M1 的动作；另一个为 M2 的状态，用来使 M 的动作能准确地模拟 M1 的动作。当 M1 执行-移动时，M2 不执行动作。,17,定理8-3,设PDA M1=(Q1,1,q01,Z0,F1)L1=L(M1)DFA M2=(Q2,2,q02,F2)L2=L

11、(M2)取 PDA M=(Q1Q2,q01,q02,Z0,F1F2)对(q,p,a,Z)(Q1Q2)()(q,p,a,Z)=(q,p,)|(q,)1(q,a,Z)且 p=(p,a),18,8.3 CFL 的判定算法,不存在判断算法的问题：CFG G，是不是二义性的？CFL L 的补是否确实不是CFL？任意两个给定 CFG 是否等价？存在判断算法的问题：CFG L 是非空语言么？CFG L 是有穷的么？一个给定的字符串 x 是 L 的句子么？,19,CFL 空否的判定,基本思想：设 L 为一个CFL，则存在 CFG G，使得 L(G)=L。由算法 6-1，可以求出等价的 CFG G，G 中不含派

12、生不出终极符号行的变量。显然，如果 NewV 中包含 G 的开始符号，则 L 就是非空的。否则，L 就是空的。因此，通过改造算法 6-1，可得到判定 L 是否为空的算法 8-1。,20,算法 8-1 判定CFL L是否为空,输入：CFG G=(V,T,P,S)。输出：G是否为空的判定；CFG G=(V,T,P,S)，V 中不含派生不出终极符号行的变量，并且有L(G)=L(G)。主要步骤：(1)OldV=；(2)NewV=A|AwP且wT*(3)while OldVNewV dobegin(4)OldV=NewV；(5)NewV=OldVAP 且(TOldV)*；end(6)V=NewV；(7)

13、P=A|AP且 AV且(TV)*；(8)if SNewV then L(G)非空 else L(G)为空,21,L 是否有穷的判定,L 为无穷，则有S*A+A+z可派生性图表示(Derivability Graph of G，DG)设CFG G=(V,T,P,S)，G的可派生性图表示是满足下列条件的有向图：(1)对于XVT，图中有且仅有一个标记为X的顶点；(2)如果AX1X2XnP，则图中存在从标记为A的顶点分别到标记为X1,X2,Xn的弧；(3)图中只有满足条件1和2的顶点和弧。G 的可派生性图表示中，任意两个顶点之间最多有一条相同方向的弧。G 的可派生性图表示表达了文法 G 中的语法变量之

14、间的派生关系。派生A+A存在的充分必要条件是 G 的可派生性图表示中存在一条从标记为A的顶点到标记为A的顶点的长度非 0 的有向回路。定理 8-6 设CFG G=(V,T,P,S)不含无用符号，L(G)为无穷语言的充分必要条件是G的可派生性图表示中存在一条有向回路。,22,L 是否有穷的判定,DG 中标记为终极符号的结点是无用的简化的可派生性图表示(simplified derivability graph of G，SDG)设CFG G=(V,T,P,S)，G 的简化的可派生性图表示是从 G的可派生性图表示中删除所有标记为终极符号的顶点后得到的图。定理 8-7 设CFG G=(V,T,P,S

15、)不含无用符号，L(G)为无穷语言的充分必要条件是G的简化的可派生性图表示中存在一条有向回路。,23,算法 8-2 判定CFL L是否为无穷语言,输入：CFG G=(V,T,P,S)。输出：G是否为无穷的判定；CFG G=(V,T,P,S)，V 中不含派生不出终极符号行的变量，并且有 L(G)=L(G)。(1)调用算法6-1,6-2；(2)if SV then L(G)为有穷的语言 else begin(3)构造G 的简化的可派生性图表示SDG；(4)if SDG中含有回路 then L(G)为无穷语言(5)else L(G)为有穷有语言。end,24,L 是否有穷的判定,给出文法SABBCC

16、|bABC|aCa增加 CABA BC CCC CABC，即 A CABC aAba,25,x 是否为 L 的句子的判定,判断 x 是否为给定文法生成的句子的根本方法是看 G 能否派生出 x。一种最简单的算法是用穷举法，这种方法又称为“试错法”,是“带回溯”的，所以效率不高。其时间复杂度为串长的指数函数。典型的自顶向下的分析方法：递归子程序法、LL(1)分析法、状态矩阵法等。典型的自底向上的分析方法：LR 分析法、算符优先分析法。这些基本的方法均只可以分析 CFG 的一个真子类。,26,CYK算法,基本思想是从 1 到|x|，找出 x 的相应长度的子串的派生变量。效率较高的根本原因是它在求 x

17、 的长度为 i 的子串 y 的“派生变量”时，是根据相应的 CNF 中的形如 ABC 的产生式，使用已经求出的 B 是 y 的前缀.的“派生变量”，而 C 是相应的后缀的“派生变量”的结果。使用 CNF，对于任给的字符串 x=x1x2xn，若 B xk，C xk+1，ABC，则 A*xk xk+1。若 B*xixk，C*xk+1xj，ABC，则 A*xi xj。用 xi,k 表示 xixi+k，Vi,k 表示能派生出xi,k的变量集合。求V1,n并检查 S 是否 是 V1,n 中的变量。时间复杂度为 O(n3)。由 Cocke,Younger 和 Kasami 在20世纪60年代分别独立提出。

18、,27,算法8-3 CYK算法,输入：CNF G=(V,T,P,S)，x；输出：xL(G)或者 x L(G)；主要数据结构：集合 Vi,j可以派生出子串 xi,k 的变量的集合。这里，xi,k 表示 x 的从第 i 个字符开始的，长度为 k 的字串。(1)for i=1 to|x|do(2)Vi,1=A|Axi,1P；(3)for k=2 to|x|do(4)for i=1 to|x|-k+1 do begin(5)Vi,k=；(6)for j=1 to k-1 do(7)Vi,k=Vi,kA|ABCP且 BVi,j且 CVi+j,k-j；end,CYK算法举例,给出Chomsky范式文法 G:SAB|BC ABA|aBCC|b CAB|a和x=baaba，判断 x 是否属于L(G)。,28,29,8.4 本章小结,(1)泵引理：与RL的泵引理类似，CFL的泵引理用来证明一个语言不是 CFL。(2)CFL 在并、乘、闭包、代换、同态映射、逆同态映射等运算下是封闭的。(3)CFL在交、补运算下是不封闭。(4)存在判定CFG产生的语言是否为空、是否有穷、是否无穷，以及一个给定的符号串是否为该文法产生的语言的一个句子的算法。,30,本章作业,1,