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

《上下文无关语言的性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1形式语言与自动机第8章上下文无关语言的性质2主要内容CFL的泵引理及其应用CFL的封闭性封闭运算：并、乘、闭包不封闭运算：交、补CFL的判定算法。判定CFG产生的语言是否为空、有穷、无穷。一个给定的符号串是否为该文法产生的语言的一个句子等问题。38.1上下文无关语言的泵引理回顾RGG=(V,T,P,S)，使得L(G)=L，当x足够长时，如

2、x

3、≥

4、V

5、+1时，存在u,v,w∈T*，

6、v

7、≥1，使得x=uvw，当G为右线性文法时，必定存在语法变量A，使得如下派生成立：S*uA*uvA*…*uviA*uv

8、iwv是可以被重复任意多次的字串！CFL也有类似性质？4上下文无关语言的泵引理CFL的自嵌套特性如果L是一个CFL，CFGG=(V,T,P,S)是产生L的文法。当L一个无穷语言时，必存在z∈L，A∈V，α,β∈(V∪T)*，且α和β中至少有一个不为ε，使得如下派生成立S*γAδ+γαAβδ+z即在文法G中，存在有如下形式的派生A+αAβ设α*v，β*x，γ*u，A*w，δ*y可以得到如下派生S*γAδ*uαAβδ*uαAβy…*uαnAβny*uvnAxny*uvnwxny5上下文无

9、关语言的泵引理引理8-1（CFL的泵引理）对于任意的CFLL，存在仅仅依赖于L的正整数N，对于任意的z∈L，当

10、z

11、≥N时，存在u,v,w,x,y，使得z=uvwxy，同时满足：(1)

12、vwx

13、≤N；(2)

14、vx

15、≥1；(3)对于任意的非负整数i，uviwxiy∈L。6上下文无关语言的泵引理用CNF作为CFL的描述工具。对于任意的z∈L，当k是z的语法树的最大路长时，必有

16、z

17、≤2k-1成立。仅当z的语法树呈上图所示的满二元树时，才有

18、z

19、=2k-1，其他时候均有

20、z

21、<2k-1。7上下文无关语言的泵引理取N=2

22、

23、V

24、=2

25、V

26、+1-1，z∈L，

27、z

28、≥N。取z的语法树中的最长的一条路p，p中的非叶子结点中必定有不同的结点标有相同的语法变量。p中最接近叶子且都标有相同的语法变量A的两个结点为v1,v2。uvwxy8上下文无关语言的泵引理z=uvwxy注意到v1-子树的最大路长小于等于

29、V

30、+1，所以，v1的结果vwx满足：

31、vwx

32、≤2(

33、V

34、+1)-1=2

35、V

36、=Nv1的后代v2标记为变量A，所以，

37、vx

38、≥1。此时有S*uAy+uvAxy+uvwxy显然，对于i=0,1,2,3,…A*viAxi+viwxi

39、所以S*uAy+uviAxiy+uviwxiy。uvwxy9例8-1证明L={anbncn

40、n≥1}不是CFL。取z=aNbNcN∈L，设z=uvwxy，主意到

41、vwx

42、≤N，所以v,w和x并在一起不能同时有3种字符。即v和x不能同时分别为a和c组成的串，也不可以取它们为形如ahbf的串。其他情况的讨论：(1)v=ah，x=bf，h+f≥1。uviwxiy=aN+(i-1)hbN+(i-1)fcN，当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。uviwxiy=aN+(i-1)hbN

43、+(i-1)fcNL。(2)v=bh，x=cf，h+f≥1。uviwxiy=aNbN+(i-1)hcN+(i-1)f当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N中至少有一个成立。uviwxiy=aNhbN+(i-1)cN+(i-1)fL。这些都与泵引理矛盾，所以，L不是CFL。10例8-1证明L={anbncn

44、n≥1}不是CFL。取z=aNbNcN∈L，设z=uvwxy，主意到

45、vwx

46、≤N，所以v,w和x并在一起不能同时有3种字符。可能出现以下几种情况：(1)v和x只包含a，取i=2，则在uv2

47、wx2y中，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)同，uv2wx2y也不在L中。(5)v或x包含两种不同的符号，例如，v包含a和b，则在uv2wx2y中将呈现a和b交错出现的情况，显然它不在L中。所以，L不是CFL。11例8-2证明L={anbmcndm

48、n,m≥1}不是CFL。取z=aNb

49、NcNdN，只需讨论如下情况：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当i≠1时，N+(i-1)h≠N和N+(i-1)f≠N至少有一个成立。uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL同理可以证明，当v=bh,x=c