可計(jì)算性與計(jì)算復(fù)雜性(計(jì)算原理答案)

1、1.6 畫出識(shí)別下述語(yǔ)言的DFA的狀態(tài)圖。a)w | w從1開始以0結(jié)束001110,10b)w | w至少有3個(gè)10100110,10,110011010c) w | w含有子串0101d) w | w的長(zhǎng)度不小于3，且第三個(gè)符號(hào)為00,100,10,1110,10e) w | w從0開始且為奇長(zhǎng)度，或從1開始且為偶長(zhǎng)度0,10,10,100,110,100,11或0,1010110f) w | w不含子串1100,10,10,10,10,10,10,1g) w | w的長(zhǎng)度不超過(guò)51110,1000h)w | w是除11和111以外的任何字符100,10,1i)w | w的奇位置均為1j)

2、 w | w至少含有2個(gè)0，且至多含有1個(gè)10010011111000,1k) ,000,10,11l) w | w含有偶數(shù)個(gè)0，或恰好兩個(gè)11100111110000001m) 空集 n) 除空串外的所有字符串0,10,10,11.29利用泵引理證明下述語(yǔ)言不是正則的。a. A1=0n1n2n | n³0。證明：假設(shè)A1是正則的。設(shè)p是泵引理給出的關(guān)于A1的泵長(zhǎng)度。令S=0p1p2p,S是A1的一個(gè)成員且S的長(zhǎng)度大于p，所以泵引理保證S可被分成3段S=xyz且滿足泵引理的3個(gè)條件。根據(jù)條件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成員。違反泵引理的條件1，矛盾。A

3、1不是正則的。b. A2=www | wÎa,b*.證明：假設(shè)A2是正則的。設(shè)p是泵引理給出的關(guān)于A2的泵長(zhǎng)度。令S=apbapbapb,S是A2的一個(gè)成員且S的長(zhǎng)度大于p，所以泵引理保證S可被分成3段S=xyz且滿足泵引理的3個(gè)條件。根據(jù)條件3，y中只含a，所以xyyz中第一個(gè)a的個(gè)數(shù)將比后兩個(gè)a的個(gè)數(shù)多，故xyyz不是A2的成員。違反泵引理的條件1，矛盾。A2不是正則的。c. A3=a2n | n³0.(在這里，a2n表示一串2n個(gè)a .)證明：假設(shè)A3是正則的。設(shè)p是泵引理給出的關(guān)于A3的泵長(zhǎng)度。令S= a2p，S是A2的一個(gè)成員且S的長(zhǎng)度大于p，所以泵引理保證S可被

4、分成3段S=xyz且滿足泵引理的3個(gè)條件。即對(duì)任意的i³0，xyiz都應(yīng)在A3中，且xyiz與xyi+1z的長(zhǎng)度都應(yīng)是2的冪. 而且xyi+1z的長(zhǎng)度應(yīng)是xyiz的長(zhǎng)度的2n倍(n³1)。于是可以選擇足夠大的i，使得|xyiz|=2n>p. 但是|xyi+1z|-|xyiz|=|y|£p. 即|xyi+1z|<2n+1, 矛盾。A3不是正則的。1.46 證明：a) 假設(shè)0n1m0n|m,n0是正則的，p是由泵引理給出的泵長(zhǎng)度。取s0p1q0p，q>0。由泵引理?xiàng)l件3知，|xy|p，故y一定由0組成，從而字符串xyyz中1前后0的數(shù)目不同，即xyy

5、z不屬于該語(yǔ)言，這與泵引理矛盾。所以該語(yǔ)言不是正則的。b) 假設(shè)0n1n|n0的補(bǔ)集是正則的，則根據(jù)正則語(yǔ)言在補(bǔ)運(yùn)算下封閉可得0n1n|n0是正則的，這與已知矛盾，故假設(shè)不成立。所以該語(yǔ)言不是正則的。c) 記c=0m1n|mn，c為c的補(bǔ)集，c0*1*=0n1n|n0，已知0n1n|n0不是正則的。若 c是正則的，由于0*1*是正則的，那么c0*1*也應(yīng)為正則的。這與已知矛盾，所以 c不是正則的。由正則語(yǔ)言在補(bǔ)運(yùn)算下的封閉性可知c也不是正則的。d) w | wÎ0,1*不是一個(gè)回文的補(bǔ)集是w | wÎ0,1*是一個(gè)回文，設(shè)其是正則的，令p是由泵引理給出的泵長(zhǎng)度。取字符串s=

6、0p1q0p，顯然s是一個(gè)回文且長(zhǎng)度大于p。由泵引理?xiàng)l件3知|xy|p，故y只能由0組成。而xyyz不再是一個(gè)回文，這與泵引理矛盾。所以w | wÎ0,1*是一個(gè)回文不是正則的。由正則語(yǔ)言在補(bǔ)運(yùn)算下的封閉性可知w | wÎ0,1*不是一個(gè)回文也不是正則的。2.4和2.5 給出產(chǎn)生下述語(yǔ)言的上下文無(wú)關(guān)文法和PDA，其中字母表S=0,1。e,1®e 1, e®10, e®ee,1®e e,1®e a. w | w至少含有3個(gè)1SA1A1A1AA0A|1A|eb. w | w以相同的符號(hào)開始和結(jié)束1,e®11,e

7、4;e0,e®e0,e®01,1®e0,0®eS0A0|1A1A0A|1A|e1,e®e0,e®e1,e®e0,e®ec. w | w的長(zhǎng)度為奇數(shù)S0A|1AA0B|1B|eB0A|1Ad. w | w的長(zhǎng)度為奇數(shù)且正中間的符號(hào)為0S0S0|1S1|0S1|1S0|01,e®00,e®e0,e®01,0®e0,0®ee,e®$e,$®e1,e®1e,1®e0,e®0e,1®ee,e®$e,$

8、74;e1,0®e0,1®ee. w | w中1比0多SA1AA0A1|1A0|1A|AA|ef. w | w=wRS0S0|1S1|1|01,e®10,e®e0,e®01,1®e0,0®ee,e®$e,$®e1,e®ee,e®eg. 空集SS2.15 用定理2.6中給出的過(guò)程，把下述CFG轉(zhuǎn)換成等價(jià)的喬姆斯基范式文法。A®BAB|B|eB®00|e解：添加新起始變?cè)猄0, 去掉B®eS0®AS0®AA®BAB|B|eA

9、74;BAB|AB|BA|B|eB®00|eB®00去掉A®e, 去掉A®BS0®AS0®AA®BAB|AB|BA|B|BBA®BAB|AB|BA|00|BBB®00B®00去掉S0®A, 添加新變?cè)猄0®BAB|AB|BA|00|BBS0®VB|AB|BA|UU|BBA®BAB|AB|BA|00|BBA®VB|AB|BA|UU|BBB®00B®UUV®BAU®03.15 證明可判定語(yǔ)言類在下列運(yùn)算下封閉。

10、a. 并。證明：設(shè)M1，M2為識(shí)別可判定語(yǔ)言A1,A2的判定器。構(gòu)造圖靈機(jī)M：M“輸入w，1) 分別在w上運(yùn)行M1和M2，每運(yùn)行一步M1就運(yùn)行一步M2。2) 若M1和M2中有一個(gè)接受，則接受。若都拒絕，則拒絕。”M為識(shí)別A1ÈA2的判定器。所以可判定語(yǔ)言類對(duì)并運(yùn)算封閉。b. 連接。證明：設(shè)M1，M2為識(shí)別可判定語(yǔ)言A1,A2的判定器。構(gòu)造圖靈機(jī)M：M“輸入w，1) 列出所有將w分成兩段的方式(|w|+1種).2) 對(duì)于每一種分段方式，在第一段上運(yùn)行M1，在第二段上運(yùn)行M2。若都接受，則接受。3) 若沒有一種分段方式被接受則拒絕。”M為識(shí)別A1A2的判定器。所以可判定語(yǔ)言類對(duì)連接運(yùn)算封

11、閉。c. 星號(hào)。證明：設(shè)M1為識(shí)別可判定語(yǔ)言A的判定器。M“輸入w，1) 列出w的所有分段的方式(2|w|-1種)。2) 對(duì)于每一種分段方式，重復(fù)下列步驟：3) 分別在每一段上運(yùn)行M1，若每一段都能被M1接受，則接受。4) 若沒有一種分段方式被接受則拒絕?！盡為識(shí)別A*的判定器。所以可判定語(yǔ)言類對(duì)星號(hào)運(yùn)算封閉。d. 補(bǔ)。證明：設(shè)M1=(Q,S,G,d,q0, q1, q2)為識(shí)別可判定語(yǔ)言A的判定器，其中q1為接受狀態(tài)，q2為拒絕狀態(tài)。令M=(Q,S,G,d,q0, q2, q1)，其中q2為接受狀態(tài)，q1為拒絕狀態(tài)。則M為識(shí)別的判定器。所以可判定語(yǔ)言類對(duì)補(bǔ)運(yùn)算是封閉的。e. 交。證明：設(shè)M1

12、，M2為識(shí)別可判定語(yǔ)言A1,A2的判定器。構(gòu)造圖靈機(jī)M：M“輸入w，1) 分別在w上運(yùn)行M1和M2，每運(yùn)行一步M1就運(yùn)行一步M2。2) 若M1和M2中都接受，則接受。若M1和M2中有一個(gè)拒絕，則拒絕?！盡為識(shí)別A1ÇA2的判定器。所以可判定語(yǔ)言類對(duì)交運(yùn)算是封閉的。3.16 證明圖靈可識(shí)別語(yǔ)言類在下列運(yùn)算下封閉：a并 b連接 c星號(hào) d交證明：要證這四種運(yùn)算下圖靈可識(shí)別語(yǔ)言類封閉，只需設(shè)計(jì)出圖靈機(jī)來(lái)識(shí)別此種語(yǔ)言。設(shè)A和B是圖靈可識(shí)別語(yǔ)言，A=L(M1)，B=L(M2)，M1和M2是兩個(gè)圖靈機(jī)。a并M=“對(duì)于輸入w：1)在輸入w上并行運(yùn)行M1和M2；2)M1和M2中有一個(gè)停機(jī)且接受，則接

13、受；若都停機(jī)且拒絕，則拒絕?！盡識(shí)別A1ÈA2。所以圖靈可識(shí)別語(yǔ)言類對(duì)并運(yùn)算是封閉的。b. 連接M“輸入w，1) 出所有將w分成兩段的方式(|w|+1種).2) 對(duì)于i=1,2,¼重復(fù)以下步驟：3) 對(duì)于每一種分段方式，在第一段上運(yùn)行M1i步，在第二段上運(yùn)行M2 i步，或者直到停機(jī)。若都接受，則接受?！盡識(shí)別A1A2。所以圖靈可識(shí)別語(yǔ)言類對(duì)連接運(yùn)算是封閉的。c星號(hào)M“輸入w，1) 列出w的所有分段的方式(2|w|-1種).2) 對(duì)于i=1,2,¼重復(fù)以下步驟：3) 對(duì)于每一種分段方式，分別在每一段上運(yùn)行M1 i步，或者直到停機(jī)。若M1接受所有段，則接受。”M識(shí)別A

14、*。所以圖靈可識(shí)別語(yǔ)言類對(duì)星號(hào)運(yùn)算是封閉的。d交M= “對(duì)于輸入w：1) 在輸入w上運(yùn)行M1。若M1接受，則轉(zhuǎn)(2)；若M1拒絕，則拒絕。2) 在w上運(yùn)行M2。若M2接受，則接受；若M2拒絕，則拒絕?！盡識(shí)別AÇB。所以圖靈可識(shí)別語(yǔ)言類對(duì)并運(yùn)算封閉。3.21 1)由cmax³|c1|知，當(dāng)|x|£1，則欲判定不等式明顯成立。2)當(dāng)|x|>1時(shí)，由 c1xn + c2xn-1 + + cnx + cn+1 = 0Þc1x =(c2 + + cnx2-n + cn+1x1-n)Þ|c1| |x| = |c2 + + cnx2-n + cn+1

15、x1-n| < |c2| + |cn|x|2-n + |cn+1| |x|1-n £ |x|>=1,當(dāng)a<=0時(shí)，|x|a <1.|c2| +.|cn| + |cn+1|x0|£ n cmax < (n + 1) cmaxÞ|x| < (n + 1) cmax / |c1|.4.11 設(shè)A=<M>|M是DFA，它不接受任何包含奇數(shù)個(gè)1的字符串。證明A是可判定的。證明：構(gòu)造DFA N，使L(N)=含奇數(shù)個(gè)1的字符串。構(gòu)造圖靈機(jī)F=“對(duì)于輸入<M>，其中M是DFA，1) 構(gòu)造DFA D，使L(D)=L(M)L

16、(N)。2) 檢測(cè)L(D)是否為空。(EDFA可判定檢測(cè))。3) 若L(D)Æ，則接受；否則拒絕?！?.13 “檢查一個(gè)CFG是否派生1*中某個(gè)串問(wèn)題”解： LX=<G>|G是0，1*上的CFG，且1*L(G)Æ證明：構(gòu)造TM TT“對(duì)于輸入<A>，A為CFG1) 將終結(jié)符“1”和“e”做標(biāo)記。2) 重復(fù)下列步驟，直至無(wú)可做標(biāo)記的變?cè)?) 如G有規(guī)則A®U1U2Un，且U1U2Un中每個(gè)符號(hào)都已做過(guò)標(biāo)記，則將A做標(biāo)記，其中Ui為終結(jié)符或非終結(jié)符。4) 如果起始變?cè)獩]有被標(biāo)記則拒絕，否則接受?！盩判定LX。5.7證明：如果A是圖靈可識(shí)別的，

17、且Am，則A是可判定的。證：AmmA且A為圖靈可識(shí)別的也為圖靈可識(shí)別的由A和都是圖靈可識(shí)別的可知A是可判定的.5.1 證明EQCFG是不可判定的。解：只須證明ALLCFGmEQCFG 即可。構(gòu)造CFG G1，使L(G1)=*。設(shè)計(jì)從ALLCFG到EQCFG的歸約函數(shù)如下：F=“對(duì)于輸入G，其中G是CFG：1） 輸出G,G1?！比鬐ÎALLCFG，則<G,G1>ÎEQCFG 。若GÏALLCFG，則<G, G1>ÏEQCFG。F將ALLCFG 歸約到EQCFG 即ALLCFGmEQCFGALLCFG是不可判定的，EQCFG是不可判定的。5.2證明EQCFG是補(bǔ)圖靈可識(shí)別的。證明：注意到ACFG=<G,w>|G是能派生串w的CFG是可判定的。構(gòu)造如下TM：F=“輸入<G,H>，其中G,H是CFG，1) 對(duì)于字符串S1, S2,¼，重復(fù)如下步驟。2) 檢測(cè)Si是否可以由G和H派生。3) 若G和H中有一個(gè)能派生w，而另一個(gè)不能，則接受。”F識(shí)別EQCFG的補(bǔ)。5.4 如果A£mB且B是正則