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

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

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

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

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

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

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

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

8、。(8分)參考答案：證明它不可判定，問題在于對于輸入串w我們假定圖靈機試圖將讀寫頭向左移，我們令P= q0,q1,qs 為M對于w結(jié)束于最左移動的最短可計算路徑，它是不可判定的。判斷下列各項的真假（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完全的。可以假定UHAMPATH，即無向圖的哈密頓路徑問題是NP完全的。參考答案：1、對于輸