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

4.1-2

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

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