资源描述:
《08 上下文无关语言性质》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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*uviwv是可以被重复任意多次的字串!CFL也有类似性质?4上下文无关语言的泵引理
8、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上下文无关语言的泵引理引理8-1(CFL的泵引理)对于任意的CFLL,存在仅仅依赖于L的正整数N,对于任意的z∈L,当
9、z
10、≥N时,存在u,v,w,x,y,使得z=
11、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、V
23、=2
24、V
25、+1-1,z∈L,
26、z
27、≥N。取z的语法树中的最长的一条路p,p中的非叶子结点中必定有不同的结点标有相同的语法变量。p中最接近叶子且都标有相同的语法变量A的两个结点为v1,v2。uvwxy8上下文无关语言的泵引理z=u
28、vwxy注意到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所以S*uAy+uviAxiy+uviwxiy。uvwxy9例8-1证明L={anbncn
39、n≥1}不是CFL。取z=aNbNcN∈L,设z=uvwxy,主意到
40、vwx
41、≤N,所以v,w和x并在一起不能同时有3种字符。即v和x不能同时分别为a和c组成的串,也不可以取它们为形如ahbf的串。其他情况的讨论:
42、(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+(i-1)fcNL。(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)fL。这些都与泵引理矛盾,所以,L不是CFL。10例8-1证明L={anbncn
43、n≥1}不是CFL。取z=aNbNcN∈L,设z=uvwxy,
44、主意到
45、vwx
46、≤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)同,uv2wx2y也不在L中。(5)v或x包含两种不同的符号,例如,v包含a和b,则在uv2wx2y中将呈现a和b交错出现的情况,显然它不在L中。所以,L不是CFL。11例8-2证明L={an
47、bmcndm
48、n,m≥1}不是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当i≠1时,N+(i-1)h≠N和N+(i-1)f≠N至少有一个成立。uviwxiy=aN+(i-1)hbN+(i-1)fcNdNL同理可以证明,当v=bh,x=c