計(jì)算理論教學(xué)資料(編輯修改稿)
2025-09-19 16:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ,”w“}∈H，iffM’ 在任何串上停機(jī)，iff M’在空串停機(jī) M‘∈L1。6. ①給定TM M，是否存在在M上停機(jī)的串？NO②給定TM M， M是否在所有上停機(jī)的串？NO設(shè)L = {M|M(a) where a∈Σ*} ，H = {M,w|M(w)停機(jī)}。尋找H到L的歸約。令f(“M”,“w”) =M’(y) = “M(w)”, M’ 輸入任何y輸出都是M在w上的模擬結(jié)果（獲得的具體做法是刪除任何輸入，寫(xiě)入w，再在w上模擬M）。{“M”,”w“}∈H，iffM’ 在任何串上停機(jī)，iff M’在任何串上停機(jī)，iff M’在所有a上停機(jī)(a∈Σ*), . M’∈L。7. 給定TM M，is L(M) finite? NO設(shè)Finite = {L(M) where L(M) isfinite}。 AH = {M,w|M accept w}存在從AH（非遞歸）到﹁Finite的遞歸函數(shù)f，f(“M”,“w”)=M’(y) = “M(w)”, 顯然f可計(jì)算。則{M,w}∈AH iff M halts on w iff M’ accept any y∈Σ*ifff(M,w) is infinite, . M’∈ ﹁Finite。由于AH歸約到﹁Finite，所以﹁Finite非確定，又∵確定性在補(bǔ)下封閉，所以Finite也是非確定的。8. 給定TM M, 帶上是否出現(xiàn)過(guò)a（a∈Σ）？NO設(shè)Write_a = {M,w|M有一條在帶上寫(xiě)a的規(guī)則}；AH = {M,w|M accept w}存在從AH（非遞歸）到﹁Finite的遞歸函數(shù)f，f(“M”,“w”)=M’(“T”,”a”) = Simulate M(w).若M接受w，在帶上寫(xiě)a；否則什么也不寫(xiě)。則{M,w}∈AH iffM halts on w iffM’在帶上寫(xiě)了一個(gè)aiff f(“M”,“w”)∈Write_a. 所以Write_a非確定。9. 給定M1，M2，它們是否在一個(gè)相同串上停機(jī)？NO設(shè)2Halts = {M1,M2|存在令他們都停機(jī)的串w}；H = {M,w|M(w)停機(jī)}構(gòu)造新機(jī)器M’，在M’帶上寫(xiě)w，模擬M1若停機(jī)則清空帶，寫(xiě)w，再模擬M2，若M2在w上也停機(jī)，則M’停機(jī)。則有M’停機(jī)iffM1,M2∈2Halt iffM1,w∈H且M2,w∈H。10. 給定M，只要M接受w，M就接受wR NO設(shè)S = {M| M accepts wRwhenever it accept w}。 AH = {M,w|M acceptw}遞歸函數(shù)f定義如下，f(M,w)= M’(y), 在M’上模擬M(w).當(dāng)M接受w時(shí)，create M’ 只接受串1111；當(dāng)M拒絕w時(shí)，create M’只接受串01。則M,w∈AH iff M接受w iff M’只接受1111 iffM’∈S，類(lèi)似的M,w?AHiffM’接受01不接受10iffM’?S判定語(yǔ)言Recursive/Recursive Enumerable / Not .1. L1 = {M| there exists an input on which M haltsin less than |M| steps} R.Test on all w less than |M|2. L2 = {M| |L(M)|4} Not .a) Reductionfrom H , .b) M,x∈非H，當(dāng)且僅當(dāng)M’屬于L23. L3 = {M| |L(M)|2} . not RTextbook Summary1. 與自然數(shù)集合N等勢(shì)的集合是可數(shù)無(wú)窮的，稱(chēng)有窮的or可數(shù)無(wú)窮的集合是可數(shù)的。非可數(shù)的集合稱(chēng)作不可數(shù)的。2. DFA( K, Σ, s, F, δ )；NFA（K,Σ，s，F(xiàn)，Δ）3. 每臺(tái)NFA都有一臺(tái)等價(jià)的DFA（method:find closure）4. 有窮自動(dòng)機(jī)接受的語(yǔ)言類(lèi)= 正則語(yǔ)言類(lèi)（正則表達(dá)式描述的語(yǔ)言類(lèi)）5. 正則語(yǔ)言在各種運(yùn)算下封閉6. 語(yǔ)言是正則的，iff其等價(jià)語(yǔ)言中有有窮個(gè)等價(jià)類(lèi)。7. DFA狀態(tài)最小化尋找等價(jià)類(lèi)（初始等價(jià)類(lèi)Famp。 KF）8. CFL（V，Σ，R，S）9. 存在非正則的CFL10. 能夠生成=兩棵語(yǔ)法分析樹(shù)的字符串的文法叫做歧義的。11. PDAM=（K，Σ，Γ，Δ，s，F(xiàn)），Γ為棧符號(hào)12. PDA接受的語(yǔ)言正好是CFL13. 正則語(yǔ)言（xynz）和CFL（uvnxynz）的泵定理14. L={anbn}∈CFL，L={anbn}?CFL但是是遞歸的，L={an,n為素?cái)?shù)}不是CFL15. Chomsky范式（CNF）：若R205。(VΣ)V2，則稱(chēng)G=（V，Σ，R，S）為Chomsky范式16. 有窮自動(dòng)機(jī)總是停機(jī)。17. CFG到CNF的轉(zhuǎn)化：1) 消除長(zhǎng)rules2) 消除空rules（Ae）3) 消除短rules（Aaor AB）18. 對(duì)任意CFLG，都可以在多項(xiàng)式時(shí)間構(gòu)造Chomsky范式G’,使得L(G’)=L(G)(Σ∪{e})19. 沒(méi)有chomsky范式能夠表示length2的字符串，所以包含2的字符串的語(yǔ)言不能轉(zhuǎn)化到chomsky范式。20. 確定型CFL（確定型PDA接受的語(yǔ)言類(lèi)）在補(bǔ)下封閉。21. TM(K，Σ，δ，s，H)，注意字母表Σ不包含←和→22. 若存在TM判定L，則稱(chēng)L是遞歸的。23. 如果對(duì)于所有w屬于Σ*，M(w) = f(w)，我們說(shuō)M計(jì)算函數(shù)f，若存在TM計(jì)算f，則f稱(chēng)為遞歸的。24. 半判定語(yǔ)言的TM都不是算法25. 多帶、多帶頭、雙向無(wú)窮帶or多維帶的TM，其判定or半判定的任何語(yǔ)言及任何函數(shù)，都分別可用標(biāo)準(zhǔn)TM判定、半判定or計(jì)算。26. 非確定型TM：一個(gè)格局可在一步里產(chǎn)生多個(gè)其他格局，NDTM is no more powerful than original TM27. 若非確定型TMM半判定或者判定語(yǔ)言L，或者計(jì)算函數(shù)f，則存在標(biāo)準(zhǔn)型TMM’半判定or判定L，or計(jì)算函數(shù)f。28. 文法是CFG的推廣，任何CFG都是文法。G=（V，Σ，R，S）29. 。30. 所有數(shù)值函數(shù)都是原始遞歸的31. 原始遞歸函數(shù)集是遞歸可枚舉的。32. 特殊語(yǔ)言/問(wèn)題：H = {“M””w”: M在w上停機(jī) }﹁H = { “M””w”：M是一臺(tái)在”w”上不停機(jī)的TM}H1 = {“M”：M在“M”上停機(jī) }﹁H1 = { w：要么w不是一臺(tái)TM的編碼，要么w是M的編碼，M是一臺(tái)在”M”上不停機(jī)的TM}H：. 。 H1：.； ﹁H, ﹁H1：.；2SAT∈P； SAT∈NP33. 沒(méi)有算法的問(wèn)題稱(chēng)作不可判定的or不可解的，如TM的停機(jī)問(wèn)題34. 證明不可判定：從通用圖靈機(jī)U通過(guò)遞歸函數(shù)歸約到L，如果L是遞歸的則U是遞歸的。，并存在L1到L2的歸約，則L2也非遞歸。
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1