計(jì)算理論-導(dǎo)引答案

4.1-2

4.104.12的證明，即證明一個(gè)語(yǔ)言是可判定的當(dāng)且僅當(dāng)有非確定的TM判定它。證明：若MM設(shè)N的不確定性分支的最大個(gè)數(shù)為b索N的不確定計(jì)算分支樹(shù)。M輸入初始化，第一帶上為w,將第一帶的內(nèi)容到第二帶上若當(dāng)前地址位為i<b，且當(dāng)前選擇無(wú)效或按當(dāng)前選擇進(jìn)入狀態(tài)，則將當(dāng)前地址位改為i+1,轉(zhuǎn)第2步；若當(dāng)前地址位為i＝b，且當(dāng)前選擇無(wú)效或按當(dāng)前選擇進(jìn)入狀態(tài)，則將當(dāng)前地址位改為空格,左移并將當(dāng)前地址位改為空格直到找到一個(gè)地址位其值<b，將當(dāng)前地址位改i+1,2步；若到了地址帶的最左端仍有當(dāng)前地址位為b，則；N1，由于NM解：枚舉器E=(Q,,,,q0,qaccept,qreject),其中轉(zhuǎn)移函數(shù)為表示若E處于狀態(tài)q,且在工作帶上讀到ar并按s1c，其中若c等于，則不打印。另外E的起始格局只能是q0v，這里v表示一個(gè)空格。檢查機(jī)的形式定義，回答下列問(wèn)題并解釋你的推測(cè)解：不能。因?yàn)閝acceptqreject字典序大于si的字符串不可能被枚舉出來(lái)。解：因?yàn)闄C(jī)的一個(gè)本質(zhì)要求是一步之內(nèi)，只能做有限的工作，而第對(duì)于問(wèn)題a.然后把3個(gè)讀寫(xiě)頭都返回到最左邊開(kāi)始讀2條帶和3條帶，每次都是讀一個(gè)字符，如果同時(shí)遇上空格對(duì)于問(wèn)題和a1步相同和a2步相同每次讀3的一個(gè)字符就讀2的兩個(gè)字符，如果同時(shí)遇上空格符，就和a1步相同和a2步相同由題知,1-pda代表一個(gè)棧的下推自,2-pda代表兩個(gè)棧的下推自。如果能用2-pda模擬一個(gè)機(jī),而已經(jīng)知道機(jī)比下推自強(qiáng)大，那么就有2-pda1-pda更強(qiáng)大。設(shè)有TMS2-pdaP，且記其兩個(gè)棧分別為A，P＝“對(duì)于輸入將w讀入棧AA中依次彈出并讀入棧B彈出b，推入棧A，記錄S的當(dāng)前狀態(tài)r。若S執(zhí)行一個(gè)左移(q,a)=(r,b,L)B的棧頂字符a替換為b；若棧AA彈出一個(gè)字符推入棧BA為空(對(duì)應(yīng)于S處于工作帶最左端)，則不作棧操作。記錄S的當(dāng)前狀態(tài)r。由上知.用2-pda模擬了機(jī),所以2-pda比1-pda強(qiáng)大下面用一個(gè)四帶TMS3-pdaP，要求P進(jìn)入接受狀態(tài)之前排空PA,B,C。SP的輸入帶，第二,三,四帶分別模擬棧A,B,C：S＝“對(duì)于輸入字符串初始化，第一帶放入w，第二，三，四帶為模擬P若P在輸入帶上讀一個(gè)非空字符，則讀第一帶字符并右移一格；P在輸入帶上讀一個(gè)，則在第一帶上不讀字符，且讀寫(xiě)頭保容一次(包括帶上得輸入?yún)^(qū)域)。證明機(jī)模型的這個(gè)變形等價(jià)于普通的機(jī)一次TMT模擬一個(gè)普通單帶TMS。在w1w2wn上并模擬S每當(dāng)S要改寫(xiě)工作帶時(shí)(例如設(shè)S要將當(dāng)前方格內(nèi)容改寫(xiě)為b，并且左移或右移一格)，T按如下方式動(dòng)作：找到帶有標(biāo)記“~”的字符，再模擬S左移或右移一格。 點(diǎn)。的證明是讓它在第一格左邊標(biāo)記“$”作為左端點(diǎn)。設(shè)有普通機(jī)M1＝(Q1,,1,1,q0,qaccept,qreject)。下面構(gòu)造與之等價(jià)的單帶雙無(wú)限帶機(jī)M2＝(Q2,,2,2,qs,qaccept,qreject)，其中},對(duì)任意2,(qt,a, (q,$,

qqsqqt2(q,a) 1(q,a),若qQ1a(q,$,R)，若qQ1a再用普通單帶機(jī)模擬單帶雙無(wú)限帶機(jī)設(shè)有單帶雙無(wú)限機(jī)M1＝(Q,,,,q0,qaccept,qreject)，下面構(gòu)造普通單帶機(jī)M2：M2=“輸入串將帶上字符串改寫(xiě)為$w,將讀寫(xiě)頭放在w按照M1的轉(zhuǎn)移函若進(jìn)入接受狀態(tài)，則接受；若進(jìn)入狀態(tài)則。也可以用普通雙帶機(jī)模擬單帶雙無(wú)限帶機(jī)設(shè)有單帶雙無(wú)限機(jī)M1＝(Q,,,,q0,qaccept,qreject)，下面構(gòu)造普通雙帶機(jī)M2：M2=“輸入串第二個(gè)帶子上放入#w,M1的轉(zhuǎn)移規(guī)則運(yùn)行，直到停機(jī)或讀寫(xiě)頭移到#上。若進(jìn)入接受狀態(tài)則接受，若進(jìn)入狀態(tài)則。若讀寫(xiě)頭移到#上，則將第一M1的轉(zhuǎn)移規(guī)則運(yùn)行，但是每一步要將讀寫(xiě)頭移動(dòng)方向反向，直到停機(jī)或讀寫(xiě)頭移到$上。若進(jìn)入接受狀態(tài)則接受，若進(jìn)入狀態(tài)則對(duì)于普通機(jī)N，構(gòu)造與之等價(jià)的帶左復(fù)位的機(jī)E：E＝“對(duì)于輸入w,在w上模擬N若N要將當(dāng)前格由a改為b若N要將當(dāng)前格由a改為b且左移，則將當(dāng)前格由a改為b#以~若N進(jìn)入接受狀態(tài)，則接受；若進(jìn)入狀態(tài)，則；否則轉(zhuǎn)第L(E)=L(N)。因此左復(fù)位的機(jī)識(shí)別可識(shí)別語(yǔ)言類(lèi)解：正則語(yǔ)言類(lèi)。首先一個(gè)DFA可以被一個(gè)以停留代替左移的機(jī)模擬。下面證明一個(gè)以停留代替左移的機(jī)S=(Q,,,,q1,qaccept,qreject)，可以被一個(gè)NFA令Q1Q×{qend}對(duì)任 1((q,),a對(duì)任意-{qaccept,qreject},若有轉(zhuǎn)移(q,a)=(r,b,R)，則令1q,ar若有轉(zhuǎn)移(q,a)=(r,b,S)，則令1q,a對(duì)任意a令1qaccept,abqaccept對(duì)任意，令Sq=(Q,,,,若L(Sq)，則令1q,{qend}。第二類(lèi)轉(zhuǎn)移是用來(lái)模擬SS沒(méi)有左移，所以右移一格之前改寫(xiě)的內(nèi)容b可以舍去。即先由1((qaccept,a),b)={(qaccept,)}讀完所有剩余字符，再由第四類(lèi)轉(zhuǎn)移中的1((qaccept,),)={qend}進(jìn)入接受S的讀寫(xiě)頭移出輸入?yún)^(qū)域的情況的，在這種情況下，S的狀態(tài)q：即若L(Sq)，則S最終會(huì)進(jìn)入接受狀態(tài)；若L(Sq)，則S最終會(huì)進(jìn)證明：設(shè)M1，M2為識(shí)別可判定語(yǔ)言A1,A2的判定器。構(gòu)造機(jī)M：M＝“輸入w，分別在w上運(yùn)行M1M2M1就運(yùn)行一步M2若M1M2中有一個(gè)接受，則接受。證明：設(shè)M1，M2為識(shí)別可判定語(yǔ)言A1,A2的判定器。構(gòu)造機(jī)M：M＝“輸入w，列出所有將w分成兩段的方式(|w|+1種若沒(méi)有一種分段方式被接受則。證明：設(shè)M1AM＝“輸入列出w的所有分段的方式(2|w|-1種)對(duì)于每一種分段方式，重復(fù)下列步若沒(méi)有一種分段方式被接受則。證明：設(shè)M1=(Q,,,,q0,q1,q2)為識(shí)別可判定語(yǔ)言A的判定器，其中q1為接受狀態(tài)，q2為狀態(tài)。令M=(Q,,,,q0,q2,q1)，其中q2為接受狀態(tài)為狀態(tài)。則M為識(shí)別A的判定器。所以可判定語(yǔ)言類(lèi)對(duì)補(bǔ)運(yùn)算是封閉的證明：設(shè)M1，M2為識(shí)別可判定語(yǔ)言A1,A2的判定器。構(gòu)造機(jī)M：M＝“輸入w，分別在w上運(yùn)行M1M2M1就運(yùn)行一步M2若M1M2若M1和M2中有一個(gè)，則。證明可識(shí)別語(yǔ)言類(lèi)在下列運(yùn)算下封閉bcd語(yǔ)言。設(shè)A和B是可識(shí)別語(yǔ)言，A=L(M1)，B=L(M2)，M1和M2是兩個(gè)在輸入w上并行運(yùn)行M1M1和M2中有一個(gè)停機(jī)且接受，則接受；若都停機(jī)且，則。M＝“輸入出所有將w分成兩段的方式(|w|+1種對(duì)于i=1,2,重復(fù)以下步對(duì)于每一種分段方式，在第一段上運(yùn)行M1i步，在第二段上運(yùn)行M＝“輸入列出w的所有分段的方式(2|w|-1種對(duì)于i=1,2,重復(fù)以下步若M1接受所有段，則接受?！盡識(shí)別A*。所以可識(shí)別語(yǔ)言類(lèi)對(duì)星號(hào)運(yùn)算是封閉的M=“對(duì)于輸入在輸入w上運(yùn)行M1。若M1接受，則轉(zhuǎn)(2)；若 在w上運(yùn)行M2。若M2接受，則接受；若 由cmax|c1|知，當(dāng)|x|1c1xn+