




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第 2 章 習(xí)題2-1設(shè)有字母表Ai =a,b,c,?, A =0,1,,試回答下列問題:(1)字母表Ai上長度為2的符號串有多少個(gè)?(2)集合AA含有多少個(gè)元素?(3)列出集合Ai(AiUA2)*中的全部長度不大于3的符號串。2-2 試分別構(gòu)造產(chǎn)生下列語言的文法:(1) anbn|n >0;(2) anbmcp|n,m,p >0;(3) an#bn|n >0 U cn#dn|n >0;(4) w#W# | w C 0,1 *,wr是 w的逆序排列;( 5)任何不是以0 打頭的所有奇整數(shù)所組成的集合;( 6)所有由偶數(shù)個(gè)0 和偶數(shù)個(gè)1 所組成的符號串的集合。2-3 試描
2、述由下列文法所產(chǎn)生的語言的特點(diǎn):1)A10S0S aAZ bAAra2)A SSS 1A0Z1A0Ar 83)A1AA B0Z1AAXB- B0EFCC 1C0CH* e4)A aSSSH*a2-4 試證明文法S AB|DC A aA|a B bBc|bc C cC|c D aDb|ab 為二義性文法。2-5 對于下列的文法A AB|c A bA|a B aSb|c試給出句子bbaacb 的最右推導(dǎo),并指出各步直接推導(dǎo)所得句型的句柄;指出句子的全部短語。2-6 化簡下列各個(gè)文法(1) SH aABS|bCACdZ bAB|cSA|cCC B bAB|cSB8cS| c(2) SHaAB|EZ
3、dDA|eB bE|fCHc AB|dSD|aAeAE fA| g(3) S-ac|bAZc BC B SACbC|d2-7消除下列文法中的e-產(chǎn)生式(1) A aAS|b2 cS| & A aAAZ bAc| dAe| &2-8消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式(1) S aB|BC A aA|c|aDbB DB|CCHbA B(2) S-SA|SB|A AtB|(S)|( )B-S| E E+T|T T -T*F|F FPf F |P P (E)|i第2章習(xí)題答案2-1 答:(1) 26*26=676 26*10=260(3) a,b,c,.,z, a0,a1,.,a9,
4、 aa,.,az,.,zz, a00,a01,.,zzz,共有26+26*36+26*36*36=34658 個(gè)2-2 解: 對應(yīng)文法為 G(S)=(S,a,b, S -e| aSb ,S)(2)對應(yīng)文法為 G(S)=(S,X,Y,a,b,c,S-aS|X, X-bX|Y, YcY| £ ,S)(3)對應(yīng)文法為 G(S)=(S,X,Y,a,b,c,d,#,S-X, AY,XaXb|#,AcYd|# ,S)W#, W 0W0|1W1|# ,S) G(S尸(S,W,R,0,1,#, S(5) G(S)=(S,A,B,I,J,0,1,234,5,6,7,8,9,S- J|IBJ,BK 0B
5、|IB|eI-J|2|4|6|8, J - 1|3|5|7|9,S)(6)對應(yīng)文法為 S 0A|1B| e , X0S|1C , B-0C|1S,CH 1A|0B2-3 解:(1)本文法構(gòu)成的語言集為:L(G尸(10) nabma0n|n,m >00(2) L(G)=1 n0n |n >0+,該語言特點(diǎn)是:產(chǎn)生的句子中,0、1個(gè)數(shù)相同,并且若干相接的1后必然緊接數(shù)量相同的連續(xù)的0o(3)本文法構(gòu)成的語言集為:L(G)=1 p1n0n|p >1,n >0 U 1 n0n0q|q >1,n>0,特點(diǎn) 是具有1p1n0n或1n0n0q形式,進(jìn)一步,可知其具有形式
6、1 n0m|n,m>0,且n+m>0。(4)由L(G)=a 2n-1|n >1可知,該語言特點(diǎn)是:產(chǎn)生的句子是奇數(shù)個(gè)a。2-4 證明:因?yàn)榇嬖诰渥樱篴bc,它對應(yīng)兩個(gè)最右推導(dǎo):SABAbc abcSDCDcabc所以,本文法具有二義性。2-5 解:句子bbaacb的最右推導(dǎo)為:S AB AaSb Aacb bAacb bbAacb bbaacb上面推導(dǎo)中,下劃線部分為當(dāng)前句型的句柄。與句子bbaacb相應(yīng)的語法樹為:全部的短語為:第一個(gè)a (a)是句子bbaacb相對于非終結(jié)符 A (A)(產(chǎn)生式 Za)的短語(直接短語);ba是句子bbaacb相對于非終結(jié)符 A的短語;bb
7、a是句子bbaacb相對于非終結(jié)符 A的短語;c是句子bbaacb相對于非終結(jié)符 S(產(chǎn)生式SHc)的短語(直接短語);acb是句子bbaacb相對于非終結(jié)符 B的短語;bbaacb(3)是句子bbaacb相對于非終結(jié)符 S(2)的短語;注:符號的上標(biāo)是為了描述方便加上去的。2-6 解:(1)因?yàn)橛煞墙K結(jié)符號 B推導(dǎo)不出終結(jié)符號串,因此 B是無用符號,含有B的產(chǎn)生 式B Bab,B cSB, S- aABS ZbAB都是無用產(chǎn)生式,應(yīng)予以刪除。因此我們最后得到與原文法等價(jià)且不含無用符號及無用產(chǎn)生式的文法為AbCACdZcSA| cCCCHcS| c(2)因?yàn)橛晌姆ǖ拈_始符號推導(dǎo)不出含有非終結(jié)符
8、號C的句型,因此C是無用符號,含有C的產(chǎn)生式CHcAB|dSD|a都是無用產(chǎn)生式,也應(yīng)予以刪除。因此我們最后得到與原文法等價(jià)且不含無用符號及無用產(chǎn)生式的文法為AaAB|EZdDA|eEfAeA E fA| g(3) 因?yàn)橛煞墙K結(jié)符號A,B 推導(dǎo)不出終結(jié)符號串,因此 A,B 是無用符號,刪除含有A,B的產(chǎn)生式 A Ba, Z cBC和B SA后得到文法 G' S:A acCH bC|d又因?yàn)橛晌姆?G S的開始符號S推導(dǎo)不出含有非終結(jié)符號 C的句型,因此C是無 用符號,含有C的產(chǎn)生式CH bC|d都是無用產(chǎn)生式,也應(yīng)予以刪除。因此我們最后得到與原文法等價(jià)且不含無用符號及無用產(chǎn)生式的文法G
9、 S 為S- ac2-7 解:(1)對于G,我們可得到 W=A;再按如下步驟彳#到產(chǎn)生式集P':對于產(chǎn)生式 S- aAS,將產(chǎn)生式 A aAS及 A aS放入P'對于產(chǎn)生式S-b,直接將產(chǎn)生式 S- b放入P'對于產(chǎn)生式 ZcS,將產(chǎn)生式 ZcS放入P'。SH aAS|aS| b(2)對于G我們可得到 W=A;再按如下步驟彳#到產(chǎn)生式集 P': 對于產(chǎn)生式 S aAA,將產(chǎn)生式 A aAA及 A A a和 A a放入P'; 對于產(chǎn)生式 A bAc,將產(chǎn)生式 A bAc及A bc放入P'對于產(chǎn)生式 Z dAe,將產(chǎn)生式 Z dAe及X de
10、放入P'。于是得到消除 一產(chǎn)生式后的文法為:S-aAA|aA| aZbAc|bc|dAe| de2-8 解:(1) 首先求出如下集合W(S)=S, W(A)=A, W(B)=B,C, W(C)=C, W(D)=D,B,C然后按如下步驟得到產(chǎn)生式集P':將P中的所有非單產(chǎn)生式添加到P,中:A aB|BC A aA|c|aDbBK DBCHbB-產(chǎn)生式的右部添加到 P中:因?yàn)镃C W(B),故將C的所有非單產(chǎn)生式的右部作為BHb因?yàn)锽C W(D),故將B的所有非單產(chǎn)生式的右部作為D-產(chǎn)生式的右部添加到 P'中:A DB因?yàn)镃C W(D),故將C的所有非單產(chǎn)生式的右部作為D-
11、產(chǎn)生式的右部添加到 P中:EKb由此得到消除單產(chǎn)生式后的文法如下:A aB|BCAK aA|c|aDbBK DB|bCKbDK b| DB因?yàn)橛晌姆ǖ拈_始符號推導(dǎo)不出含有非終結(jié)符號A的句型,因此A是無用符號,含有A的產(chǎn)生式 Z aA|c|aDb都是無用產(chǎn)生式,應(yīng)予以刪除。于是得到消除無用產(chǎn)生式和單產(chǎn)生式后的文法如下:SH aB|BCBK DB|bCbAb| DB(2) 首先求出如下集合W(S)=S,A,B, W(A)=A,B, W(B)=B然后按如下步驟得到產(chǎn)生式集P':將P中的所有非單產(chǎn)生式添加到P,中:SHSA|SBZ (S)|( )B S|S-產(chǎn)生式的右部添加到 P中:S-產(chǎn)生式
12、的右部添加到 P中:A-產(chǎn)生式的右部添加到 P中:因?yàn)锳C W(S),故將A的所有非單產(chǎn)生式的右部作為A (S)|()因?yàn)锽C W(S),故將B的所有非單產(chǎn)生式的右部作為A S|因?yàn)锽C W(A),故將B的所有非單產(chǎn)生式的右部作為z S|由此得到消除單產(chǎn)生式后的文法如下:A SASB|(S)|( )|S|z (S)|( )|S|BH S|(3) 首先求出如下集合W(E)=E,T,F,P, W(T)=T,F,P, W(F)=F,P, W(P)=P然后按如下步驟得到產(chǎn)生式集P':將P中的所有非單產(chǎn)生式添加到P,中:1 E+T T T*FFPfFP (E)|i因?yàn)門,F,P C W(E),故將T,F,P的所有非單產(chǎn)生式的右部作為E-產(chǎn)生式的右部添加到P'中:E- T*FEPfFE (E)|i因?yàn)?/p>
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 銀行承兌擔(dān)保協(xié)議書
- 深入解析計(jì)算機(jī)二級試題及答案
- 蘇州簽訂重磅協(xié)議書
- 社交場合中的邏輯思維應(yīng)用試題及答案
- 風(fēng)險(xiǎn)管理中的倫理因素試題及答案
- 邏輯能力在財(cái)務(wù)管理中的重要性試題及答案
- 邏輯規(guī)則與推理題型總結(jié)試題及答案
- 法律綜合復(fù)試題型及答案
- 法律專業(yè)測試題及答案解析
- 法律援助結(jié)構(gòu)化面試題及答案
- 十二生肖調(diào)查報(bào)告
- 健身塑形瑜伽學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年
- 2024-2025年遼寧省面試真題
- 單位駕駛員勞務(wù)派遣投標(biāo)方案投標(biāo)文件(技術(shù)方案)
- 資本經(jīng)營-終結(jié)性考試-國開(SC)-參考資料
- 2024年浙江省中考科學(xué)試卷
- 拆除工程地坪拆除施工方案
- 軟件授權(quán)書范本
- 招聘筆試題與參考答案(某大型國企)2025年
- 平房區(qū)全面推進(jìn)信訪工作法治化測試練習(xí)試卷附答案
- 2024年山東省中考英語試卷十二套合卷附答案
評論
0/150
提交評論