計算理論習題答案CHAP3new

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

若N要將當前格由a改為b且右移，則照此動作；

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