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