




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、形式語(yǔ)言與自動(dòng)機(jī)課后作業(yè)答案第二章4找出右線性文法,能構(gòu)成長(zhǎng)度為1至5個(gè)字符且以字母為首的字符串。答:G=N,T,P,S其中N=S,A,B,C,D T=x,y 其中x所有字母 y所有的字符 P如下:Sx SxA Ay AyB By ByC Cy CyD Dy6構(gòu)造上下文無(wú)關(guān)文法能夠產(chǎn)生L=/a,b*且中a的個(gè)數(shù)是b的兩倍答:G=N,T,P,S其中N=S T=a,b P如下:Saab Saba SbaaSaabS SaaSb SaSab SSaabSabaS SabSa SaSba SSabaSbaaS SbaSa SbSaa SSbaa7找出由下列各組生成式產(chǎn)生的語(yǔ)言(起始符為S)(1) SS
2、aS Sb(2) SaSb Sc(3) Sa SaE EaS答:(1)b(ab)n /n0或者L=(ba)nb /n0(2) L=ancbn /n0(3) L=a2n+1 /n0第三章1 下列集合是否為正則集,若是正則集寫出其正則式。(1) 含有偶數(shù)個(gè)a和奇數(shù)個(gè)b的a,b*上的字符串集合(2) 含有相同個(gè)數(shù)a和b的字符串集合(3) 不含子串a(chǎn)ba的a,b*上的字符串集合答:(1)是正則集,自動(dòng)機(jī)如下奇a偶b偶a偶b a a b b b b奇a奇b偶a奇b a a(2) 不是正則集,用泵浦引理可以證明,具體見17題(2)。(3) 是正則集先看L為包含子串a(chǎn)ba的a,b*上的字符串集合顯然這是正則
3、集,可以寫出表達(dá)式和畫出自動(dòng)機(jī)。(略)則不包含子串a(chǎn)ba的a,b*上的字符串集合L是L的非。根據(jù)正則集的性質(zhì),L也是正則集。4對(duì)下列文法的生成式,找出其正則式(1) G=(S,A,B,C,D,a,b,c,d,P,S),生成式P如下:SaA SBAabS AbBBb BcCCD DbBDd(2) G=(S,A,B,C,D,a,b,c,d,P,S),生成式P如下:SaA SBAcC AbBBbB BaCD CabBDd答:(1) 由生成式得:S=aA+B A=abS+bB B=b+cC C=D D=d+bB 式化簡(jiǎn)消去CD,得到B=b+c(d+bB)即B=cbB+cd+b =>B=(cb)*
4、(cd+b) 將代入S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+)(cb)*(cd+b)(2) 由生成式得:S=aA+B A=bB+cC B=a+bB C=D+abB D=dB 由得 B=b*a 將代入 C=d+abb*a=d+ab+a 將代入 A=b+a+c(d+b+a) 將代入 S=a(b+a+c(d+ab+a)+b*a =ab+a+acd+acab+a+b*a5.為下列正則集,構(gòu)造右線性文法:(1)a,b*(2)以abb結(jié)尾的由a和b組成的所有字符串的集合(3)以b為首后跟若干個(gè)a的字符串的集合(4) 含有兩個(gè)相繼a和兩個(gè)相繼b的由
5、a和b組成的所有字符串集合答:(1)右線性文法G=(S,a,b,P,S)P: SaS SbS S(2) 右線性文法G=(S,a,b,P,S)P: SaS SbS Sabb(3) 此正則集為ba*右線性文法G=(S,A,a,b,P,S)P: SbA AaA A(4) 此正則集為a,b*aaa,b*bba,b*, a,b*bba,b*aaa,b*右線性文法G=(S,A,B,C,a,b,P,S)P: SaS/bS/aaA/bbB AaA/bA/bbCBaB/bB/aaCCaC/bC/7.設(shè)正則集為a(ba)*(1) 構(gòu)造右線性文法(2) 找出(1)中文法的有限自動(dòng)機(jī)答:(1)右線性文法G=(S,A,
6、a,b,P,S)P: SaA AbS A(2)自動(dòng)機(jī)如下:P2P1 ab(p2是終結(jié)狀態(tài))9.對(duì)應(yīng)圖(a)(b)的狀態(tài)轉(zhuǎn)換圖寫出正則式。(圖略)(1) 由圖可知q0=aq0+bq1+a+ q1=aq2+bq1 q0=aq0+bq1+a=>q1=abq1+bq1+aaq0+aa=(b+ab) q1+aaq0+aa=(b+ab) *( aaq0+aa)=>q0=aq0+b(b+ab) *( aaq0+aa ) +a+= q0(a+b (b+ab) *aa)+ b(b+ab) *aa+a+=(a+b (b+ab) *aa) *(b+ab) *aa+a+)=(a+b (b+ab) *aa)
7、 *(3) q0=aq1+bq2+a+bq1=aq0+bq2+bq0=aq1+bq0+a=>q1=aq0+baq1+bbq0+ba+b=(ba)*(aq0 +bbq0+ba+b)=>q2=aaq0+abq2+bq0+ab+a=(ab)*(aaq0 +bq0+ ab+a)=>q0=a(ba)*(a+bb) q0 + a(ba)*(ba+b)+b(ab)*(aa+b)q0+ b(ab)*(ab+a)+a+b=a(ba)*(a+bb) +b(ab)*(aa+b)* (a(ba)*(ba+b)+ b(ab)*(ab+a)+a+b)10.設(shè)字母表T=a,b,找出接受下列語(yǔ)言的DFA:(
8、1) 含有3個(gè)連續(xù)b的所有字符串集合(2) 以aa為首的所有字符串集合(3) 以aa結(jié)尾的所有字符串集合答:(1)M=(q0,q1 q2,q3,a,b,q0,q3),其中如下:abq0q0q1q1q0q2q2q0q3q3q3q3(2)M=(q0,q1 q2 ,a,b,q0,q2),其中如下:abq0q1q1q2q2q2q2(3)M=(q0,q1 q2 ,a,b,q0,q2),其中如下:abq0q1q0q1q2q0q2q2q014構(gòu)造DFA M1等價(jià)于NFA M,NFA M如下:(1)M=(q0,q1 q2,q3,a,b,q0,q3),其中如下:(q0,a)=q0,q1 (q0,b)=q0(q1
9、,a)=q2 (q1,b)= q2 (q2,a)=q3 (q2,b)= (q3,a)=q3 (q3,b)= q3 (2)M=(q0,q1 q2,q3,a,b,q0, q1,q2),其中如下:(q0,a)=q1,q2 (q0,b)=q1(q1,a)=q2 (q1,b)= q1,q2 (q2,a)=q3 (q2,b)= q0(q3,a)= (q3,b)= q0答:(1)DFA M1=Q1, a,b,1, q0, q0,q1,q3,q0,q2,q3,q0, q1,q2,q3其中Q1 =q0,q0,q1, q0,q1,q2, q0,q2, q0,q1, q2,q3, q0,q1, q3, q0,q2,
10、 q3, q0,q31滿足abq0q0,q1 q0q0,q1q0,q1,q2 q0,q2q0,q1,q2 q0,q1, q2,q3 q0,q2 q0,q2 q0,q1, q3q0 q0,q1, q2,q3 q0,q1, q2,q3 q0,q2, q3 q0,q1, q3 q0,q1, q2,q3 q0,q2, q3 q0,q2, q3 q0,q1, q3 q0,q3 q0,q3 q0,q1, q3 q0,q3(2)DFA M1=Q1, a,b,1, q0, q1,q3, q1,q3,q0,q1,q2,q1,q2 ,q1,q2,q3,q2,q3其中Q1 =q0,q1,q3, q1,q2, q0,
11、q1,q2,q1,q2,q3, q1,q2,q3,q2,q31滿足abq0q1,q3q1q1,q3q2 q0,q1,q2q1q2q1,q2q2q3q0 q0,q1,q2q1,q2,q3 q0,q1,q2q1,q2q2,q3 q0,q1,q2q3q0q1,q2,q3q2,q3 q0,q1,q2q2,q3q3q015. 15.對(duì)下面矩陣表示的-NFAabcP(起始狀態(tài))pqrqpqrr(終止?fàn)顟B(tài))qrp(1) 給出該自動(dòng)機(jī)接收的所有長(zhǎng)度為3的串(2) 將此-NFA轉(zhuǎn)換為沒有的NFA答:(1)可被接受的的串共 23個(gè),分別為aac, abc, acc, bac, bbc, bcc, cac, cbc
12、, ccc, caa, cab, cba, cbb, cca, ccb, bba, aca, acb, bca, bcb, bab, bbb, abb(2)-NFA:M=(p,q,r,a,b,c,p,r) 其中如表格所示。因?yàn)?closure(p)= 則設(shè)不含的NFA M1=(p,q,r,a,b,c,1,p,r)1(p,a)=(p,a)=-closure(p,),a)=p1(p,b)=(p,b)=-closure(p,),b)=p,q1(p,c)=(p,c)=-closure(p,),c)=p,q,r1(q,a)=(q,a)=-closure(q,),a)=p,q1(q,b)=(q,b)=-c
13、losure(q,),b)=p,q,r1(q,c)=(q,c)=-closure(q,),c)=p,q,r1(r,a)=(r,a)=-closure(r,),a)=p,q,r1(r,b)=(r,b)=-closure(r,),b)=p,q,r1(r,c)=(r,c)=-closure(r,),c)=p,q,r圖示如下:(r為終止?fàn)顟B(tài))pq b,c a,b,c a,b,c a,b,c c a,b,c b,c a,b,cr a,b,c16設(shè)NFA M=(q0,q1,a,b,q0,q1),其中如下:(q0,a)=q0,q1 (q0,b)=q1(q1,a)= (q1,b)= q0, q1構(gòu)造相應(yīng)的DF
14、A M1,并進(jìn)行化簡(jiǎn)答:構(gòu)造一個(gè)相應(yīng)的DFA M1=Q1, a,b,1, q0, q1,q0,q1其中Q1 =q0,q1,q0,q11滿足abq0q0,q1q1q1q0,q1q0,q1q0,q1q0,q1由于該DFA已是最簡(jiǎn),故不用化簡(jiǎn)17.使用泵浦引理,證明下列集合不是正則集:(1) 由文法G的生成式SaSbS/c產(chǎn)生的語(yǔ)言L(G)(2) /a,b*且有相同個(gè)數(shù)的a和b(3) akcak/k1(4) /a,b*證明:(1)在L(G)中,a的個(gè)數(shù)與b的個(gè)數(shù)相等假設(shè)L(G)是正則集,對(duì)于足夠大的k取= ak (cb)kc令=102因?yàn)閨0|>0 |10|k 存在0使10i2L所以對(duì)于任意0
15、只能取0=an n(0,k)則10i2= akn(an)i(cb)kc 在i不等于0時(shí)不屬于L與假設(shè)矛盾。則L(G)不是正則集(2)假設(shè)該集合是正則集,對(duì)于足夠大的k取= ak bk令=102因?yàn)閨0|>0 |10|k 存在0使10i2L所以對(duì)于任意0只能取0=an n(0,k)則10i2= akn(an)ibk 在i不等于0時(shí)a與b的個(gè)數(shù)不同,不屬于該集合與假設(shè)矛盾。則該集合不是正則集(3)假設(shè)該集合是正則集,對(duì)于足夠大的k取= ak cak令=102因?yàn)閨0|>0 |10|k 存在0使10i2L所以對(duì)于任意0只能取0=an n(0,k)則10i2= akn(an)icak 在i不等于0時(shí)c前后a的個(gè)數(shù)不同,不屬于該集合與假設(shè)矛盾。則該集合不是正則集(4)假設(shè)該集合是正則集,對(duì)于足夠大的k取= ak bakb令=102因?yàn)閨0|>0 |10|k 存在0使10i2L所以對(duì)于任意0只能取0=an n(0,k)則10i2= akn(an)ibakb 在i不等于0時(shí)不滿足的形式,不屬于該集合與假設(shè)矛盾。
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 多功能城市水系統(tǒng)的優(yōu)化與綜合利用
- 2025至2030全球及中國(guó)零售業(yè)務(wù)管理軟件行業(yè)發(fā)展趨勢(shì)分析與未來投資戰(zhàn)略咨詢研究報(bào)告
- 影視后期制作專業(yè)發(fā)展規(guī)劃
- 固態(tài)電池漸行漸近、新技術(shù)及工藝持續(xù)涌現(xiàn)
- 2025至2030國(guó)內(nèi)生物飼料行業(yè)發(fā)展趨勢(shì)分析與未來投資戰(zhàn)略咨詢研究報(bào)告
- 2025至2030全球及中國(guó)聲控?zé)粜袠I(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)自行式吊桿升降機(jī)行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)自定義程序托盤行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國(guó)自動(dòng)絲網(wǎng)印刷行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025至2030中國(guó)腹腔鏡內(nèi)窺鏡行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 2025年中國(guó)LTCC技術(shù)行業(yè)市場(chǎng)現(xiàn)狀、前景分析研究報(bào)告(智研咨詢發(fā)布)
- 租賃住房培訓(xùn)課件下載
- DL∕T 5161.5-2018 電氣裝置安裝工程質(zhì)量檢驗(yàn)及評(píng)定規(guī)程 第5部分:電纜線路施工質(zhì)量檢驗(yàn)
- 湖北武漢洪山區(qū)招考聘用社區(qū)干事235人模擬檢測(cè)試卷【共1000題含答案解析】
- DB4451-T 1-2021《地理標(biāo)志產(chǎn)品+鳳凰單叢(樅)茶》-(高清現(xiàn)行)
- 信訪工作課品課件
- 加油站火災(zāi)、爆炸事故現(xiàn)場(chǎng)處置方案
- IPQC技能培訓(xùn)
- 2022年(詳細(xì)版)高中數(shù)學(xué)學(xué)業(yè)水平考試知識(shí)點(diǎn)
- 常用樂高零件清單
- 蛋糕制作工藝課件(PPT81張)
評(píng)論
0/150
提交評(píng)論