計(jì)算理論習(xí)題答案CHAP3new

3.3修改定理3.10以得到推論3.12的證明，即證明一個(gè)語言是可判定的當(dāng)且僅當(dāng)有非確定的TM判定它。證明：若M是一個(gè)確定型判定器則，則M也是一個(gè)非確定型判定器?，F(xiàn)在設(shè)N是一個(gè)非確定的判定器，將構(gòu)造一個(gè)與之等價(jià)的確定型判定器M。模擬過程使用深度搜索。 設(shè)N的不確定性分支的最大個(gè)數(shù)為b。M有三個(gè)帶：一個(gè)輸入帶，一個(gè)工作帶，一個(gè)地址帶。M按深度優(yōu)先方式搜索N的不確定計(jì)算分支樹。 M=“輸入w，初始化，第一帶上為w,第二帶為空，第三帶為1;將第一帶的內(nèi)容復(fù)制到第二帶上，按當(dāng)前地址位數(shù)字選擇N的一個(gè)不確定性分支，在第二帶上模擬N運(yùn)行一步；若當(dāng)前地址位為i<b，且當(dāng)前選擇無效或按當(dāng)前選擇進(jìn)入拒絕狀態(tài)，則將當(dāng)前地址位改為i+1,轉(zhuǎn)第2步；若當(dāng)前地址位為i＝b，且當(dāng)前選擇無效或按當(dāng)前選擇進(jìn)入拒絕狀態(tài)，則將當(dāng)前地址位改為空格,左移并將當(dāng)前地址位改為空格直到找到一個(gè)地址位其值<b，將當(dāng)前地址位改為i+1,轉(zhuǎn)第2步；若到了地址帶的最左端仍有當(dāng)前地址位為b，則拒絕；若N進(jìn)入接受狀態(tài)，則接受；否則，右移一格，將空格上寫入1，轉(zhuǎn)第三步?！庇捎贜是非確定型判定器，所以對(duì)任意輸入，由本題的提示M一定會(huì)停機(jī)。3.4給出枚舉器的形式定義。解：枚舉器E=(Q,,,,q0,qaccept,qreject),其中轉(zhuǎn)移函數(shù)為： ：Q×Q××{L,R}×* (q,a)=(r,b,s1,c) 表示若E處于狀態(tài)q,且在工作帶上讀到a，則狀態(tài)轉(zhuǎn)移為r，當(dāng)前格改寫為b并按s1作相應(yīng)左或右移，打印帶上寫下字符串c，其中若c等于，則不打印。另外E的起始格局只能是q0v，這里v表示一個(gè)空格。3.5檢查圖靈機(jī)的形式定義，回答下列問題并解釋你的推測(cè)：圖靈機(jī)能在它的帶子上寫下空白符嗎b．帶字母表和輸入字母表能相同嗎？c．圖靈機(jī)的讀寫頭能在連續(xù)的兩步中處于同一個(gè)位置嗎？d．圖靈機(jī)能只包含一個(gè)狀態(tài)嗎？解：a．能。因?yàn)榭瞻追麑儆趲ё帜副?；b．不能。因?yàn)榭瞻追粚儆谳斎胱帜副?；c．能。當(dāng)讀寫頭處于左端點(diǎn)時(shí)，如果轉(zhuǎn)移是向左轉(zhuǎn)移，因?yàn)椴粶?zhǔn)機(jī)器從帶的左端點(diǎn)移出，所以下一個(gè)格局讀寫頭仍在左端點(diǎn)。d．不能。因?yàn)閝acceptqreject，至少應(yīng)有兩個(gè)狀態(tài)。3.6解：因?yàn)镸不一定是判定器，可能會(huì)在運(yùn)行某個(gè)si時(shí)不停機(jī)，則L(M)中按字典序大于si的字符串不可能被枚舉出來。3.7解：因?yàn)閳D靈機(jī)的一個(gè)本質(zhì)要求是一步之內(nèi)，只能做有限的工作，而第1)步中取所有可能的值，這有無限多種情況。3.8構(gòu)造具有3條帶的圖靈機(jī)。對(duì)于問題a.w先讀入第一條帶，然后讀到0就把0寫入第2條帶，讀到1就把1寫入第3條帶，直到讀到空格為止。然后把3個(gè)讀寫頭都返回到最左邊。開始讀第2條帶和第3條帶，每次都是讀一個(gè)字符，如果同時(shí)遇上空格符，則接收，否則拒絕。對(duì)于問題b:和a的第1步相同。和a的第2步相同。每次讀帶3的一個(gè)字符就讀帶2的兩個(gè)字符，如果同時(shí)遇上空格符，就接收，否則拒絕。對(duì)于問題c:和a的第1步相同。和a的第2步相同。每次讀帶3的一個(gè)字符就讀帶2的兩個(gè)字符，如果同時(shí)遇上空格符，就拒絕，否則接受。3.9由題知,1-pda代表一個(gè)棧的下推自動(dòng)機(jī),2-pda代表兩個(gè)棧的下推自動(dòng)機(jī)。如果能用2-pda模擬一個(gè)圖靈機(jī),而我們已經(jīng)知道圖靈機(jī)比下推自動(dòng)機(jī)強(qiáng)大，那么就有2-pda比1-pda更強(qiáng)大。設(shè)有TMS。下面構(gòu)造2-pdaP，且記其兩個(gè)棧分別為A，B：P＝“對(duì)于輸入w,1) 將w讀入棧A，再全部從棧A中依次彈出并讀入棧B。2) 模擬S在w上運(yùn)行。記錄S的當(dāng)前狀態(tài)，并且棧B的棧頂字符為S的讀寫頭所指方格的字符：若S執(zhí)行一個(gè)右移(q,a)=(r,b,R)，則將棧B的棧頂字符a替換為b，彈出b，推入棧A，記錄S的當(dāng)前狀態(tài)r。若S執(zhí)行一個(gè)左移(q,a)=(r,b,L)，首先將棧B的棧頂字符a替換為b；若棧A不空，則將棧A彈出一個(gè)字符推入棧B；若棧A為空(對(duì)應(yīng)于S處于工作帶最左端)，則不作棧操作。記錄S的當(dāng)前狀態(tài)r。3) 若S進(jìn)入接受狀態(tài)，則進(jìn)入接受狀態(tài)?！庇缮现?我們用2-pda模擬了圖靈機(jī),所以2-pda比1-pda強(qiáng)大.下面用一個(gè)四帶TMS來模擬一個(gè)3-pdaP，要求P進(jìn)入接受狀態(tài)之前排空棧，并且或者推入或者彈出：記P的三個(gè)棧為A,B,C。S的四個(gè)帶，第一帶用來模擬P的輸入帶，第二,三,四帶分別模擬棧A,B,C：S＝“對(duì)于輸入字符串w，初始化，第一帶放入w，第二，三，四帶為空。模擬P分別在四個(gè)帶上按如下方式動(dòng)作：若P在輸入帶上讀一個(gè)非空字符，則讀第一帶字符并右移一格；若P在輸入帶上讀一個(gè)，則在第一帶上不讀字符，且讀寫頭保持不動(dòng)。棧A,B,C中若有彈出，則在相應(yīng)帶上當(dāng)前格改寫為空格，并左移一格；若有推入a，則在相應(yīng)帶上右移一格，并寫入a。3) 若P進(jìn)入接受狀態(tài)，則接受。”3.10證明雙無限帶圖靈機(jī)識(shí)別圖靈可識(shí)別語言。證明思路：利用雙無限單帶圖靈機(jī)模擬普通單帶圖靈機(jī)時(shí)，只需要設(shè)計(jì)一個(gè)左端點(diǎn)。我們的證明是讓它在第一格左邊標(biāo)記“$”作為左端點(diǎn)。證明：首先用單帶雙無限帶圖靈機(jī)模擬普通單帶圖靈機(jī)：設(shè)有普通圖靈機(jī)M1＝(Q1,,1,1,q0,qaccept,qreject)。下面構(gòu)造與之等價(jià)的單帶雙無限帶圖靈機(jī)M2＝(Q2,,2,2,qs,qaccept,qreject)，其中Q2=Q1{qs,qt},qs為新的起始狀態(tài)；2＝1{$}.對(duì)任意qQ2,a2,再用普通單帶圖靈機(jī)模擬單帶雙無限帶圖靈機(jī)：設(shè)有單帶雙無限圖靈機(jī)M1＝(Q,,,,q0,qaccept,qreject)，下面構(gòu)造普通單帶圖靈機(jī)M2：M2=“輸入串w，將帶上字符串改寫為$w,將讀寫頭放在w的第一個(gè)字符上，按照M1的轉(zhuǎn)移函數(shù)運(yùn)行，每當(dāng)讀寫頭移到了$上，就將$右邊的所有字符右移一格，并在$右邊的方格里寫上空格符，再將讀寫頭放在這個(gè)方格上，轉(zhuǎn)第二步，若進(jìn)入接受狀態(tài)，則接受；若進(jìn)入拒絕狀態(tài)則拒絕?！币部梢杂闷胀p帶圖靈機(jī)模擬單帶雙無限帶圖靈機(jī)：設(shè)有單帶雙無限圖靈機(jī)M1＝(Q,,,,q0,qaccept,qreject)，下面構(gòu)造普通雙帶圖靈機(jī)M2：M2=“輸入串w，在第一個(gè)帶上放上$,讀寫頭放在$上；第二個(gè)帶子上放入#w,讀寫頭放在第二個(gè)方格上。當(dāng)?shù)谝粠ёx寫頭位于$上，而第二帶讀寫頭不在＃上時(shí)，在第二帶上按照M1的轉(zhuǎn)移規(guī)則運(yùn)行，直到停機(jī)或讀寫頭移到#上。若進(jìn)入接受狀態(tài)則接受，若進(jìn)入拒絕狀態(tài)則拒絕。若讀寫頭移到#上，則將第一帶上讀寫頭右移一格。當(dāng)?shù)诙ёx寫頭位于#上，而第一帶讀寫頭不在$上時(shí)，在第一帶上按照M1的轉(zhuǎn)移規(guī)則運(yùn)行，但是每一步要將讀寫頭移動(dòng)方向反向，直到停機(jī)或讀寫頭移到$上。若進(jìn)入接受狀態(tài)則接受，若進(jìn)入拒絕狀態(tài)則拒絕。若讀寫頭移到$上，則將第二帶上讀寫頭右移一格，轉(zhuǎn)第二步。”3.11只寫一次圖靈機(jī)是一個(gè)單帶圖靈機(jī)，它在每個(gè)帶方格上最多只能改變其內(nèi)容一次(包括帶上得輸入?yún)^(qū)域)。證明圖靈機(jī)模型的這個(gè)變形等價(jià)于普通的圖靈機(jī)模型。證明：普通單帶圖靈機(jī)總是可以模擬只寫一次圖靈機(jī)。下面說明怎樣用一個(gè)只寫一次TMT模擬一個(gè)普通單帶TMS。T=“對(duì)于輸入w=w1w2wn,1) 在w1w2wn上并模擬S運(yùn)行。2) 每當(dāng)S要改寫工作帶時(shí)(例如設(shè)S要將當(dāng)前方格內(nèi)容改寫為b，并且左移或右移一格)，T按如下方式動(dòng)作：a.將當(dāng)前方格改寫為“b*”，在帶子右邊第一個(gè)空格寫下“#”。b.將“#”左邊的字符抄寫到“#”右邊(注：每抄寫一個(gè)字符，需要將此格字符改寫一次以作上標(biāo)記，但是“b*”不用再作另外標(biāo)記，而且將“b*”抄寫為“b~”)。c.找到帶有標(biāo)記“~”的字符，再模擬S左移或右移一格。然后繼續(xù)模擬S。3) 若S接受則接受；若S拒絕則拒絕?！?.12對(duì)于普通圖靈機(jī)N，構(gòu)造與之等價(jià)的帶左復(fù)位的圖靈機(jī)E：E＝“對(duì)于輸入w,在w上模擬N的一步動(dòng)作：

若N要將當(dāng)前格由a改為b且右移，則照此動(dòng)作；

若N要將當(dāng)前格由a改為b且左移，則將當(dāng)前格由a改為b#且復(fù)位：以~標(biāo)記當(dāng)前位，右移一格；若當(dāng)前位沒有標(biāo)記#，則復(fù)位，右移直到找到標(biāo)記有~的字符，去掉此標(biāo)記，右移一格轉(zhuǎn)步(a);若當(dāng)前位有標(biāo)記#，則去掉標(biāo)記#并復(fù)位，右移或直到找到標(biāo)記有~的字符，去掉此標(biāo)記；若N進(jìn)入接受狀態(tài)，則接受；若進(jìn)入拒絕狀態(tài)，則拒絕；否則轉(zhuǎn)第一步。”L(E)=L(N)。因此左復(fù)位的圖靈機(jī)識(shí)別圖靈可識(shí)別語言類。3.13以停留代替左移的圖靈機(jī)識(shí)別什么語言類？解：正則語言類。首先一個(gè)DFA可以被一個(gè)以停留代替左移的圖靈機(jī)模擬。下面證明一個(gè)以停留代替左移的圖靈機(jī)S=(Q,,,,q1,qaccept,qreject)，可以被一個(gè)NFAM=(Q1,,1,q0,F)模擬。M的構(gòu)造如下：令Q1=Q×{qend}，F(xiàn)={qend}，q0=(q1,),對(duì)任意qQ-{qaccept,qreject},a,令1((q,),a)={(q,a)};對(duì)任意qQ-{qaccept,qreject},a,若有轉(zhuǎn)移(q,a)=(r,b,R)，則令1((q,a),)={(r,)};若有轉(zhuǎn)移(q,a)=(r,b,S)，則令1((q,a),)={(r,b)};對(duì)任意a,b，令1((qaccept,a),b)={(qaccept,)};對(duì)任意qQ，令Sq=(Q,,,,q,qaccept,qreject),若L(Sq)，則令1((q,),)={qend}。其中第一類轉(zhuǎn)移是用來讀字符的。第二類轉(zhuǎn)移是用來模擬S的讀寫頭的移動(dòng)的。由于S沒有左移，所以右移一格之前改寫的內(nèi)容b可以舍去。第三類轉(zhuǎn)移用來處理當(dāng)S已進(jìn)入接受狀態(tài)，但是字符串還沒有讀完的情況的。即先由1((qaccept,a),b)={(qaccept,)}讀完所有剩余字符，再由第四類轉(zhuǎn)移中的1((qaccept,),)={qend}進(jìn)入接受狀態(tài)。第四類轉(zhuǎn)移用來處理S的讀寫頭移出輸入?yún)^(qū)域的情況的，在這種情況下，S是進(jìn)入接受狀態(tài)，還是進(jìn)入拒絕狀態(tài)，還是不停機(jī)，完全取決于進(jìn)入空白區(qū)域時(shí)的狀態(tài)q：即若L(Sq)，則S最終會(huì)進(jìn)入接受狀態(tài)；若L(Sq)，則S最終會(huì)進(jìn)入拒絕狀態(tài)或不停機(jī)。3.15證明可判定語言類在下列運(yùn)算下封閉。a.并。證明：設(shè)M1，M2為識(shí)別可判定語言A1,A2的判定器。構(gòu)造圖靈機(jī)M： M＝“輸入w，分別在w上運(yùn)行M1和M2，每運(yùn)行一步M1就運(yùn)行一步M2。若M1和M2中有一個(gè)接受，則接受。若都拒絕，則拒絕?！盡為識(shí)別A1A2b.連接。證明：設(shè)M1，M2為識(shí)別可判定語言A1,A2的判定器。構(gòu)造圖靈機(jī)M： M＝“輸入w，列出所有將w分成兩段的方式(|w|+1種).對(duì)于每一種分段方式，在第一段上運(yùn)行M1，在第二段上運(yùn)行M2。若都接受，則接受。若沒有一種分段方式被接受則拒絕。”M為識(shí)別A1A2的判定器。所以可判定語言類對(duì)連接運(yùn)算封閉。c.星號(hào)。證明：設(shè)M1為識(shí)別可判定語言A的判定器。M＝“輸入w，列出w的所有分段的方式(2|w|-1種)。對(duì)于每一種分段方式，重復(fù)下列步驟：分別在每一段上運(yùn)行M1，若每一段都能被M1接受，則接受。若沒有一種分段方式被接受則拒絕?！盡為識(shí)別A*的判定器。所以可判定語言類對(duì)星號(hào)運(yùn)算封閉。d.補(bǔ)。證明：設(shè)M1=(Q,,,,q0,q1,q2)為識(shí)別可判定語言A的判定器，其中q1為接受狀態(tài)，q2為拒絕狀態(tài)。令M=(Q,,,,q0,q2,q1)，其中q2為接受狀態(tài)，q1為拒絕狀態(tài)。則M為識(shí)別的判定器。所以可判定語言類對(duì)補(bǔ)運(yùn)算是封閉的。e.交。證明：設(shè)M1，M2為識(shí)別可判定語言A1,A2的判定器。構(gòu)造圖靈機(jī)M： M＝“輸入w，分別在w上運(yùn)行M1和M2，每運(yùn)行一步M1就運(yùn)行一步M2。若M1和M2中都接受，則接受。若M1和M2中有一個(gè)拒絕，則拒絕?！盡為識(shí)別A1A23.16證明圖靈可識(shí)別語言類在下列運(yùn)算下封閉：a．并b．連接c．星號(hào)d．交證明：要證這四種運(yùn)算下圖靈可識(shí)別語言類封閉，只需設(shè)計(jì)出圖靈機(jī)來識(shí)別此種語言。設(shè)A和B是圖靈可識(shí)別語言，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ī)且接受，則接受；若都停機(jī)且拒絕，則拒絕?！盡識(shí)別A1A2b.M＝“輸入w，出所有將w分成兩段的方式(|w|+1種).對(duì)于i=1,2,重復(fù)以下步驟：對(duì)于每一種分段方式，在第一段上運(yùn)行M1i步，在第二段上運(yùn)行M2i步，或者直到停機(jī)。若都接受，則接受。”M識(shí)別A1A2。所以圖靈可識(shí)別語言類對(duì)連接運(yùn)算是封閉的。c．M＝“輸入w，列出w的所有分段的方式(2|w|-1種).對(duì)于i=1,2,重復(fù)以下步驟：對(duì)于每一種分段方式，分別在每一段上運(yùn)行M1i步，或者直到停機(jī)。若M1接受所有段，則接受?！盡識(shí)別A*。所以圖靈可識(shí)別語言類對(duì)星號(hào)運(yùn)算是封閉的。d．M=“對(duì)于輸入w：在輸入w上運(yùn)行M1。若M1接受，則轉(zhuǎn)(2)；若M1拒絕，則拒絕。在w上運(yùn)行M2。若M2接受，則接受；若M2拒絕，則拒絕?！盡識(shí)別AB。所以圖靈可識(shí)別語言類對(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+…+c