2007級(jí)-計(jì)算理論-試卷答案(共3頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)計(jì)算理論 試題答案（2007級(jí)）證明：設(shè)M是一臺(tái)識(shí)別語言B的DFA，交換M的接受狀態(tài)與非接受狀態(tài)得到一臺(tái)新的DFA，則這臺(tái)新DFA識(shí)別B的補(bǔ)集。因而，正則語言類在補(bǔ)運(yùn)算下封閉。(8分)參考答案：設(shè)M是一臺(tái)將DFAM的接受態(tài)與非接受態(tài)交換后的DFA，接下來證明M識(shí)別B語言，則M識(shí)別B的補(bǔ)集：假定M識(shí)別x，則對(duì)于x 在M上運(yùn)行將結(jié)束于M的一個(gè)接受態(tài)，因?yàn)镸和M交換了接受態(tài)與非接受態(tài)，因此對(duì)于x運(yùn)行于M，將會(huì)結(jié)束于一個(gè)非接受態(tài)，所以x/B。類似地，如果x不被M接受，則它一定被

2、M接受。故M恰好接受所有不被M接受的那些串，因此M識(shí)別B的補(bǔ)集。 既然B是任意的正則語言，且我們已構(gòu)造出一臺(tái)自動(dòng)機(jī)識(shí)別它的補(bǔ)集，它表明任何正則語言的補(bǔ)也是正則的。因此，正則語言類在補(bǔ)運(yùn)算下封閉。令0，1，和ADDx=y+z | x，y，z是二制整數(shù)，且x是y與z的和，證明ADD不是正則的。(8分)參考答案：假定ADD是正則的。讓P作為泵引理中的泵長度，選擇S的串形式為1P0P1P作為ADD的一個(gè)成員。因?yàn)镾有長度大于P，由泵引理保證它能分割成形如：Sxyz的三部分，滿足泵引理的條件。泵引理的第三個(gè)條件有xyP，它表明對(duì)于K1，y就是1K。這是xy2z是串1PKOP1P，而它不是ADD的成員，由

3、泵引理導(dǎo)出矛盾，因此ADD不是正則的。請(qǐng)將下述CFG轉(zhuǎn)換成等價(jià)的喬姆斯基范式文法。(8分)ABABBB00參考答案：S0ABCCBABDBBAABCCBABDBBBCCC0DAB請(qǐng)用泵引理證明語言A 0n02n03n | n0 不是上下文無關(guān)的。(8分)參考答案：由泵引理，讓P作為泵長度，s=0p02p03p ，接下來證明s=uvxyz不能進(jìn)行泵抽取。v和y都不能包含，否則，xv2wy2z將超過2個(gè)s ，因此，如果我們按s將s分成三段如：0p，02p，03p，至少有一段不包含v或y。因此，由于段之間的1：2：3的比例不再維持，xv2wy2z也不語言A中。故語言A 0n02n03n | n0 不

4、是上下文無關(guān)。的下面的語言都是字母表0,1上的語言，請(qǐng)以實(shí)現(xiàn)描述水平級(jí)給出判定這些語言的圖靈機(jī)：(8分)1、Aww包含相同個(gè)數(shù)的0和1。2、Bww所包含的0的個(gè)數(shù)是1的個(gè)數(shù)的二倍。參考答案：1、對(duì)于輸入串w1)、掃描帶子且標(biāo)記第一個(gè)沒有被標(biāo)記的0，如果沒有未被標(biāo)記的0，則跳到第4步，否則，將指針移到帶子的最前端。2)、掃描帶子且標(biāo)記第一個(gè)沒有被標(biāo)記的1，如果沒有未被標(biāo)記的1，則拒絕。3)、將指針移到帶子的最前端且重復(fù)第1步4)、將指針移到帶子的最前端，掃描帶子看是否還有未被標(biāo)記的1，如果沒有則接受，否則拒絕。2、略只寫一次圖靈機(jī)是一個(gè)單帶圖靈機(jī)，它在每個(gè)帶方格上最多只能改變其內(nèi)容一次（包括帶上

5、的輸入?yún)^(qū)）。證明圖靈機(jī)模型的這個(gè)變形等價(jià)于普通的圖靈機(jī)模型。(8分)參考答案：我們首先模擬一個(gè)可以寫兩次的普通圖靈機(jī)，這個(gè)寫兩次的圖靈機(jī)相當(dāng)于一個(gè)單帶圖靈機(jī)通過將整帶內(nèi)容考貝到帶子已用部分的右邊來實(shí)現(xiàn)。考貝過程通過一個(gè)一個(gè)字符地操作，標(biāo)記已考貝的字符。這個(gè)過程改變帶子兩次，一次是寫字符，另一次是標(biāo)記它被考貝。標(biāo)記在帶子上，當(dāng)在標(biāo)記位置考貝時(shí)，帶子的內(nèi)容按照?qǐng)D靈機(jī)更新。為了便于寫一次圖靈機(jī)模擬，除每個(gè)格子用兩個(gè)格子代替外，其它操作如前面一致。第一個(gè)用來寫原始內(nèi)容，第二個(gè)用來寫標(biāo)記內(nèi)容。這樣就可以模擬寫兩次圖靈機(jī)，依此類推，可以模擬寫N次圖靈機(jī)。因此圖靈機(jī)模型的這個(gè)變形等價(jià)于普通的圖靈機(jī)模型。設(shè)A

6、MM是DFA，它不接受任何包含奇數(shù)個(gè)1的串，證明A是可判定的。(8分)參考答案：如下的TM X 判定AX=“ 對(duì)于輸入，M是DFA構(gòu)造一個(gè)DFA O ，接受任何包含奇數(shù)個(gè)1的串構(gòu)造DFA B 使依據(jù)定理4.4，對(duì)于輸入B運(yùn)行TM T， T判定EDFA如果T接受，則接受。否則T拒絕，則拒絕。設(shè)C是一個(gè)語言。證明C是圖靈可識(shí)別的，當(dāng)且僅當(dāng)存在一個(gè)可判定語言D，使得Cxy （x，yD）。(8分)參考答案：要求從兩個(gè)方向證明。首先，我們假定D是存在的，TM識(shí)別C對(duì)于輸入x ，查找y 使得D。如果y 找到則接受，否則繼續(xù)找。另一方向，假定C被圖靈機(jī)M 識(shí)別。定義一語言B為 |x在|y|內(nèi)接受X。語言B是

7、可判定的，且如果xc，則M在有限步內(nèi)接受x，因此對(duì)于足夠長的y 有B，但如果x/c 則對(duì)于任意y有/c因此C是圖靈可識(shí)別的，當(dāng)且僅當(dāng)存在一個(gè)可判定語言D，使得Cxy （x，yD）證明所有的圖靈可識(shí)別問題都映射可歸約到ATM。(8分)參考答案：假定L是圖靈可識(shí)別的，且有圖靈機(jī)M識(shí)別它。為將L歸約到ATM ，我們標(biāo)記任何 的串X 。這時(shí)xL等價(jià)于ATM.此外，映射是可計(jì)算的，因此它給出了從L到ATM的映射歸約。因此所有的圖靈可識(shí)別問題都映射可歸約到ATM ?？紤]這樣的問題，檢查圖靈機(jī)在輸入w上，當(dāng)其讀寫頭處于帶最左方格時(shí)，是否曾經(jīng)試圖將讀寫頭向左移。將這個(gè)問題形式化為一個(gè)語言，并證明它是不可判定的

8、。(8分)參考答案：證明它不可判定，問題在于對(duì)于輸入串w我們假定圖靈機(jī)試圖將讀寫頭向左移，我們令P= q0,q1,qs 為M對(duì)于w結(jié)束于最左移動(dòng)的最短可計(jì)算路徑，它是不可判定的。判斷下列各項(xiàng)的真假（T或F）(10分)1、2n=O(n) 2、n2=O(n)3、n2=O(log2n) 4、nlogn=O(n2) n n5、22 =O(22 ) 6、 n=o(2n)7、2n=o(n2) 8、 2n=o(3n)9、1=o(n) 10、 n=o(logn)參考答案：1、T 2、F 3、F 4、T 5、T 6、F 7、T 8、T 9、T 10、F十二、設(shè)G表示無向圖，令(10分)SPATH=G，a，b，kG包含從a到b，長度至多為k的簡單路徑LPATH=G，a，b，kG包含從a到b，長度至少為k的簡單路徑證明SPATHP證明LPATH是NP完全的?？梢约俣║HAMPATH，即無向圖的哈密頓路徑問題是NP完全的。參考答案：1、對(duì)于輸