2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩19頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、形式語言與自動(dòng)機(jī)理論試題形式語言與自動(dòng)機(jī)理論試題一、按要求完成下列填空1.給出集合ΦΦ和集合ε000的冪集(2x4)(1)ΦΦΦΦΦ(2)Φε000ε0ε00000ε0002.設(shè)∑=01請(qǐng)給出∑上的下列語言的文法(2x5)(1)所有包含子串01011的串S→X01011YX→ε|0X|1XY→ε|0Y|1Y(2)所有既沒有一對(duì)連續(xù)的0,也沒有一對(duì)連續(xù)的1的串A→ε|A’|A”A’→0|01|01A’A”→1|10|10A”3.構(gòu)造識(shí)別下

2、列語言的DFA2x6(1)x|x?0,1且x以0開頭以1結(jié)尾(設(shè)置陷阱狀態(tài),當(dāng)?shù)谝粋€(gè)字符為1時(shí),進(jìn)入陷阱狀態(tài))1S0110010(2)x|x?0,1且x的第十個(gè)字符為1(設(shè)置一個(gè)陷阱狀態(tài),一旦發(fā)現(xiàn)x的第十個(gè)字符為0,進(jìn)入陷阱狀態(tài))1S0101010101100101010101二、判斷(正確的寫T,錯(cuò)誤的寫F)5x21.設(shè)1R和2R是集合abcde上的二元關(guān)系,則3231321)(RRRRRRR???=aaabbbccc推導(dǎo)二:S=aS

3、BC=aaSBCBC=aaaBCBCBC=aaaBBCCBC=aaaBBCBCC=aaabBCBCC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccC=aaabbbccc四、判斷語言nnn010|n=1是否為RL,如果是,請(qǐng)構(gòu)造出它的有窮描述(FARG或者RL);如果不是,請(qǐng)證明你的結(jié)論(12分)解:設(shè)L=nnn010|n=1。假設(shè)L是RL,則它滿足泵引理。不妨設(shè)N是泵引理所指的僅依賴于

4、L的正整數(shù),取Z=顯然,Z∈L。NNN010按照泵引理所述,必存在u,v,w。由于|uv|=1,所以v只可能是由0組成的非空串。不妨設(shè)v=,k=1此時(shí)有u=,w=從而有uvw=k0jkN??0NNj010i當(dāng)i=2時(shí),有uvw=又因?yàn)閗=1NNjikjkN010)0(0??2NNkN010?所以NkN這就是說不屬于L,NNkN010?這與泵引理矛盾。所以,L不是RL。五、構(gòu)造等價(jià)于下圖所示DFA的正則表達(dá)式。(12分)答案(之一):(0

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論