資源描述：
《上下文無關(guān)語言的性質(zhì).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1形式語言與自動機(jī)第8章上下文無關(guān)語言的性質(zhì)2主要內(nèi)容CFL的泵引理及其應(yīng)用CFL的封閉性封閉運(yùn)算：并、乘、閉包不封閉運(yùn)算：交、補(bǔ)CFL的判定算法。判定CFG產(chǎn)生的語言是否為空、有窮、無窮。一個給定的符號串是否為該文法產(chǎn)生的語言的一個句子等問題。38.1上下文無關(guān)語言的泵引理回顧RGG=(V,T,P,S)，使得L(G)=L，當(dāng)x足夠長時，如
2、x
3、≥
4、V
5、+1時，存在u,v,w∈T*，
6、v
7、≥1，使得x=uvw，當(dāng)G為右線性文法時，必定存在語法變量A，使得如下派生成立：S?*uA?*uvA?*…?*uviA?*uv
8、iwv是可以被重復(fù)任意多次的字串！CFL也有類似性質(zhì)？4上下文無關(guān)語言的泵引理CFL的自嵌套特性如果L是一個CFL，CFGG=(V,T,P,S)是產(chǎn)生L的文法。當(dāng)L一個無窮語言時，必存在z∈L，A∈V，α,β∈(V∪T)*，且α和β中至少有一個不為ε，使得如下派生成立S?*γAδ?+γαAβδ?+z即在文法G中，存在有如下形式的派生A?+αAβ設(shè)α?*v，β?*x，γ?*u，A?*w，δ?*y可以得到如下派生S?*γAδ?*uαAβδ?*uαAβy…?*uαnAβny?*uvnAxny?*uvnwxny5上下文無
9、關(guān)語言的泵引理引理8-1（CFL的泵引理）對于任意的CFLL，存在僅僅依賴于L的正整數(shù)N，對于任意的z∈L，當(dāng)
10、z
11、≥N時，存在u,v,w,x,y，使得z=uvwxy，同時滿足：(1)
12、vwx
13、≤N；(2)
14、vx
15、≥1；(3)對于任意的非負(fù)整數(shù)i，uviwxiy∈L。6上下文無關(guān)語言的泵引理用CNF作為CFL的描述工具。對于任意的z∈L，當(dāng)k是z的語法樹的最大路長時，必有
16、z
17、≤2k-1成立。僅當(dāng)z的語法樹呈上圖所示的滿二元樹時，才有
18、z
19、=2k-1，其他時候均有
20、z
21、<2k-1。7上下文無關(guān)語言的泵引理取N=2
22、
23、V
24、=2
25、V
26、+1-1，z∈L，
27、z
28、≥N。取z的語法樹中的最長的一條路p，p中的非葉子結(jié)點(diǎn)中必定有不同的結(jié)點(diǎn)標(biāo)有相同的語法變量。p中最接近葉子且都標(biāo)有相同的語法變量A的兩個結(jié)點(diǎn)為v1,v2。uvwxy8上下文無關(guān)語言的泵引理z=uvwxy注意到v1-子樹的最大路長小于等于
29、V
30、+1，所以，v1的結(jié)果vwx滿足：
31、vwx
32、≤2(
33、V
34、+1)-1=2
35、V
36、=Nv1的后代v2標(biāo)記為變量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，設(shè)z=uvwxy，主意到
41、vwx
42、≤N，所以v,w和x并在一起不能同時有3種字符。即v和x不能同時分別為a和c組成的串，也不可以取它們?yōu)樾稳鏰hbf的串。其他情況的討論：(1)v=ah，x=bf，h+f≥1。uviwxiy=aN+(i-1)hbN+(i-1)fcN，當(dāng)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當(dāng)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，設(shè)z=uvwxy，主意到
45、vwx
46、≤N，所以v,w和x并在一起不能同時有3種字符。可能出現(xiàn)以下幾種情況：(1)v和x只包含a，取i=2，則在uv2
47、wx2y中，a的個數(shù)明顯大于b,c的個數(shù)，因此它不在L中。(2)v和x只包含b或只包含c，理由與(1)同，uv2wx2y也不在L中。(3)v只包含a,x只包含b，取i=2，則在uv2wx2y中，a,b的個數(shù)將超過c的個數(shù)，它不在L中。(4)v只包含b,x只包含c，理由與(3)同，uv2wx2y也不在L中。(5)v或x包含兩種不同的符號，例如，v包含a和b，則在uv2wx2y中將呈現(xiàn)a和b交錯出現(xiàn)的情況，顯然它不在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種情況。設(shè)v=ah,x=bf，并且h+f≥1uviwxiy=aN+(i-1)hbN+(i-1)fcNdN當(dāng)i≠1時，N+(i-1)h≠N和N+(i-1)f≠N至少有一個成立。uviwxiy=aN+(i-1)hbN+(i-1)fcNdN?L同理可以證明，當(dāng)v=bh,x=c
