下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
選(b)(a)B是A0、1、2三個數(shù)字編碼出停選(a)AB,AB的補,這個(b(c)選(b)“M”?L(MMDFA的編碼的集合。M“M”的字符總會讀完讀完的時候是終結(jié)狀態(tài)就接受否則就說“M”?L(M),M*yes,否則反之。因此就知道選(b)了。regularDFADFA是否接受這個字符DFA是否能接受自己的編碼,它木有能力模擬和判斷別人,所DFAPDAPDA是非確定性的,然后只要一條路是接受了“MMPDA的其中一些運算不一定可以停機,它完全可以在某條路上死循環(huán)給不出接受的答案。因此,這是個非遞歸的co-r.e.的問題,選擇(c(A∪BAB了。解析:用泵定理證明。設(shè)L2={anbn},L2包含于L1。給定整數(shù)k,考慮字符串w=akbk,w∈L2,我們可以把w重寫為w=xyz,且|xy|≤k,且y≠e,即y=ai,i>0.但是xz=ak-ibk?L2,與泵定理。所以L1不是正則的。(a)G=(V,Σ,R,S)}Sp為初始狀態(tài)}L5不是遞歸可枚舉的??梢杂脤腔碜C明,詳細說明同見164頁LNP完全的。本人水平有限,不知道完全的證明需要什么ingredient。個人認為方法有兩種,F(xiàn)n 我們?nèi)稳∑渲袀€子句來驗證,即驗 1
Tik個子句被滿足的布爾表達式,那么,要判定是否存在滿足至少k個子句的真值,就變成了一個ΣTi(i從1到Cnk)SAT問題,而且歸約的時間是多項式時間內(nèi)的。因此,MAX-SAT
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 員工聘用協(xié)議書2023
- 個人租房的合同協(xié)議書范本10篇
- 再婚離婚協(xié)議書2025年
- 重癥肌無力樣綜合征病因介紹
- T-CIECCPA 011-2024 高雜貴金屬冶煉渣資源化處理技術(shù)規(guī)范
- 中考歷史復(fù)習第一部分教材知識速查模塊2中國近代史第1講列強的侵略與中國人民的抗爭公開課一等獎省
- (2024)汽車內(nèi)飾用品項目可行性研究報告寫作范本(一)
- 2023年金屬門窗及類似制品項目融資計劃書
- 2023年紡織產(chǎn)品項目籌資方案
- 《開環(huán)伯德圖的繪制》課件
- 機械CAD、CAM-形考任務(wù)一-國開-參考資料
- 電氣專業(yè)述職報告
- 腰椎病的中醫(yī)護理查房
- 2024年湖南省公務(wù)員考試《行測》真題及答案解析
- 成都錦城學院《操作系統(tǒng)與nux管理》2022-2023學年期末試卷
- 《弧弦圓心角》說課稿課件
- 中職班級建設(shè)三年規(guī)劃方案
- 河南省鄭州市2023-2024學年高二上學期期末考試 物理 含解析
- 2024年中級安全工程師《(建筑施工)安全生產(chǎn)專業(yè)實務(wù)》考試題庫(含答案)
- 弘揚抗戰(zhàn)精神課程設(shè)計
- 康復(fù)護理完整版
評論
0/150
提交評論