形式語言與自動機理論-蔣宗禮-第四章參考答案.doc

《形式語言與自動機理論-蔣宗禮-第四章參考答案.doc》由會員分享，可在線閱讀，更多相關《形式語言與自動機理論-蔣宗禮-第四章參考答案.doc（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1.寫出表示下列語言的正則表達式。 （吳賢珺 02282047） ⑴ {0, 1}*。 解：所求正則表達式為：(0+1)*。 ⑵ {0, 1}+。 解：所求正則表達式為：(0+1)+。 ⑶ { x│x∈{0,1}+ 且x中不含形如00的子串 }。 解：根據(jù)第三章構造的FA，可得所求正則表達式為：1*(01+)*(01+0+1)。 ⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。 解：根據(jù)上題的結果，可得所求正則表達式為：ε+1*(01+)*(01+0+1)。 ⑸ { x│x∈{0,1}+ 且x中含形如10110的子串 }。 解：所求正則表達式為：(0+1)*10110(0+1)*。 ⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。 解：根據(jù)第三章的習題，接受x的FA為： S 0 1 1 0 q0 q1 q2 1 0 1 1 1 0 q3 q4 要求該FA對應的正則表達式，分別以q0、q1、q2、q3、q4為終結狀態(tài)考慮： q0為終態(tài)時的正則表達式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)* q1為終態(tài)時的正則表達式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q2為終態(tài)時的正則表達式：0*11*0((10)*(111*11*0)*(00*11*0)*)* q3為終態(tài)時的正則表達式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4為終態(tài)時的正則表達式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)* 將以上5個正則表達式用“+”號相連，就得到所要求的正則表達式。 ⑺ { x│x∈{0,1}+ 且當把x看成二進制數(shù)時，x模5與3同余和x為0時，│x│=1 且x≠0時，x的首字符為1}。 解：先畫出狀態(tài)轉(zhuǎn)移圖，設置5個狀態(tài)q0、q1、q2、q3、q4，分別表示除5的余數(shù)是0、1、2、3、4的情形。另外，設置一個開始狀態(tài)q.由于要求x模5和3同余，而3模5余3,故只有q3可以作為終態(tài)。由題設，x=0時，│x│=1，模5是1，不符合條件，所以不必增加關于它的狀態(tài)。下面對每一個狀態(tài)考慮輸入0和1時的狀態(tài)轉(zhuǎn)移。 q: 輸入1，模5是1，進入q1。 q0: 設x=5n。輸入0，x=5n*2=10n，模5是0，故進入q0 輸入1，x=5n*2+1=10n+1，模5是1，故進入q1 q1：設x=5n+1。輸入0，x=(5n+1)*2=10n+2，模5是2，故進入q2 輸入1，x=(5n+1)*2+1=10n+3，模5是3，故進入q3 q2：設x=5n+2。輸入0，x=(5n+2)*2=10n+4，模5是4，故進入q4 輸入1，x=(5n+2)*2+1=10n+5，模5是0，故進入q0 q3：設x=5n+3。輸入0，x=(5n+3)*2=10n+6，模5是1，故進入q1 輸入1，x=(5n+3)*2+1=10n+7，模5是2，故進入q2 q4：設x=5n+4。輸入0，x=(5n+4)*2=10n+8，模5是3，故進入q3 輸入1，x=(5n+4)*2+1=10n+9，模5是4，故進入q4 則狀態(tài)轉(zhuǎn)移圖如下： q 1 q1 S 0 1 q2 q3 0 q4 1 0 1 0 1 q0 0 1 則所求的正則表達式為：1(010*1+(1+001*0)(101*0)*(0+110*1))*(1+001*0)(101*0)* ⑻ { x│x∈{0,1}+ 且x的第10個字符是1 }。 解：所求正則表達式為：(0+1)91(0+1)*。 ⑼ { x│x∈{0,1}+ 且x以0開頭以1結尾 }。 解：所求正則表達式為：0(0+1)*1。 ⑽ { x│x∈{0,1}+ 且x中至少含兩個1 }。 解：所求正則表達式為：(0+1)*1(0+1)*1(0+1)*。 ⑾ { x│x∈{0,1}*和如果x以1結尾，則它的長度為偶數(shù)；如果x以0結尾，則它的長度為奇數(shù)}。 解：所求正則表達式為：(0+1)2n+11+(0+1)2n0 (n∈N) 或0+(0+1)((0+1)(0+1))*1+(0+1)(0+1)((0+1)(0+1))*0。 ⑿ { x│x是十進制非負實數(shù) }。 解：首先定義∑＝{ .,0,1,2,3,4,5,6,7,8,9} 則所求正則表達式為：(0+1+…+9)*. (0+1+…+9)*。 ⒀ Φ。 解：所求正則表達式為：Φ。 ⒁ {ε}。 解：所求正則表達式為：ε。 ********************************************************************************* 2.理解如下正則表達式，說明它們表示的語言 （1）(00+11)+表示的語言特征是0和1都各自成對出現(xiàn) （2）(1+0)*0100+表示的語言特征是以010后接連續(xù)的0結尾 （3）(1+01+001)*(e+0+00) 表示的語言特征是不含連續(xù)的3個0 （4）((0+1)(0+1))*+ ((0+1)(0+1)(0+1))* 表示所有長度為3n或2m的0，1串（n0,m0） （5）((0+1)(0+1))* ((0+1)(0+1)(0+1))* 表示所有長度為3n+2m的0，1串（n0,m0） （6）00+11+（01+10）（00+11）*（10+01）表示的語言特征為長度為偶數(shù)n的串.當n=2時，是00或11的串。n4時，是以01或10開頭，中間的子串00或11成對出現(xiàn)，最后以10或01結尾的串 ********************************************************************************************* 4.3.證明下列各式 褚穎娜 02282072 （1）結合律 (rs)t=r(st) (r+s)+t= r+(s+t) 1）證明 對" x∈(rs)t 總可以找到一組x1 x2 x3 使得 x=x1x2x3 其中x3∈t x1x2∈rs 且 x1∈r, x2∈s, 則 x2x3∈st 因此x1(x2x3)∈r(st) 即 x1x2x3∈r(st) x∈r(st)得證 因此 (rs)tr(st) 同理可證r(st) (rs)t 則 (rs)t=r(st) 成立 2) 證明 對"x∈(r+s)+t x∈(r+s)或x∈t 對于x∈r+sx∈r或r∈s ， 因此x∈r或x∈s或x∈tx∈r或x∈(s+t) x∈r+(s+t) 所以(r+s)+t r+(s+t) 同理可證r+(s+t) (r+s)+t 則(r+s)+t= r+(s+t) 成立 （2）分配律 r(s+t)=rs+rt (s+t)r=sr+tr 1) 證明 對于"x∈r(s+t) 總可以找到x1 x2 使得x=x1x2 其中x1∈r, x2∈（s+t） 由x2∈（s+t） x2∈s或x2∈t 則x1x2∈rs或x1x2∈rt 所以r(s+t)rs+rt 對于"x∈rs+rt x∈rs或x∈rt 且總可以找到一組x1 x2 使得x=x1x2 其中x1∈r, x2∈s或x1∈r, x2∈tx1∈r，x2∈s或x2∈t x1∈r，x2∈(s+t) x1x2∈r(s+t) 所以rs+rtr(s+t) 則r(s+t)=rs+rt 2) 證明 對于"x∈(s+t)r 總可以找到x1 x2 使得x=x1x2 其中 x1∈（s+t），x2∈r 由x1∈（s+t） x1∈s或x1∈t 則x1x2∈sr或x1x2∈tr 所以(s+t)rsr+tr 對于"x∈sr+tr x∈sr或x∈tr 且總可以找到一組x1 x2 使得x=x1x2 其中x1∈s, x2∈r或x1∈t, x2∈r x1∈s或x1∈t, x2∈r x1∈(s+t) ,x2∈r x1x2∈(s+t)r 所以sr+tr (s+t)r 則(s+t)r=sr+tr (3)交換律 r+s=s+r 證明 對于 "x∈r+sx∈r或x∈sx∈s或x∈rx∈s+r 所以r+ss+r 同理可證s+r∈r+s 則r+s=s+r （4）冪等律 r+r=r 證明 對于 " x∈r+r x∈r或x∈r x∈r 所以r+rr 對于 "x∈rx∈r或x∈rx∈r+r 所以rr+r 因此 r+r=r （5）加法運算零元素：r+F=r 證明 對于 " x∈r+F x∈r或x∈F x∈r 所以r+Fr 對于 "x∈rx∈r或x∈Fx∈r+F 所以rr+F 因此 r+F=r (6) 乘法運算單位元：rε=εr=r 證明：∵對"xR xe=ex=x ∴R{e}={e}R=R ∴re=er=r (7)乘法運算零元素：r=r= 證明：∵對"xR x=x= ∴R{}={}R=R ∴r=r= (8) F*=ε 證明F*=F0∪F1∪F2∪F3…...=ε∪F1∪F2∪F3…...=ε (9) (r+ε)*=r* 由第一章的作業(yè)1.30中的第九題 (L1∪{ε})*=L1*其中L1為正則語言 又r為正則表達式 正則語言可以用正則表達式表示，因此顯然有(r+ε)*=r*成立 (10) (r*s*)*=(r+s)* 由第一章的作業(yè)1.30中的第八題 (L2∪L1)*=( L2* L1*)* 其中L1、L2 為正則語言 又r、s為正則表達式 正則語言可以用正則表達式表示，因此顯然有(r+s)*= (r*s*)*成立 即(r*s*)*=(r+s)*成立 (11) (r*)*=r* 由第一章的作業(yè)1.30中的第三題 (L1*)*= L1*其中L1為正則語言 又r為正則表達式 正則語言可以用正則表"達式表示，因此顯然有(r*)*= r*成立 ********************************************************************************* 4下面各式成立嗎？請證明你的結論 (1) (r+rs)*r=r(sr+r)* 證明：成立。 如果對所有的k>=0, (r+rs)k r=r(sr+r)k 成立，則(r+rs)*r=r(sr+r)*肯定成立 可以用歸納法證明(r+rs)k r=r(sr+r)k對所有的k>=0成立 I. k=0時候，(r+rs)0 r=r= r(sr+r)0 II. 假設k=n時候(r+rs)nr=r(sr+r)n成立，往證k=n+1時候結論成立 (r+rs)n+1r=(r+rs)n (r+rs)r=(r+rs)n (rr+rsr)= (r+rs)n r (r+sr)= r(sr+r)n (r+sr) = r(sr+r)n (sr+r)= r(sr+r)n+1 這就是說，結論對k=n+1成立，即證明了(r+rs)k r=r(sr+r)k對所有的k>=0成立，所以(r+rs)*r=r(sr+r)* (2) t(s+t)r=tr+tsr 證明：不成立。不妨取r=0,s=1,t=2,則t(s+t)r=2(1+2)0=210+230,但tr+tsr=20+210. (3) rs=sr 證明：不成立。不妨取r=0,s=1,顯然rs=01,而sr=10. (4) s(rs+s)*r=rr*s(rr*s)* 不成立，假設r,s分別是表示語言R，S的正則表達式，例如當R={0}，S={1}, L(s(rs+s)*r)是以1開頭的字符串，而L(rr*s(rr*s)*)是以0開頭的字符串.L(s(rs+s)*r) L(rr*s(rr*s)*) 所以s(rs+s)*r rr*s(rr*s)*,結論不成立 (5)(r+s)*=(r*s*)* 證明：結論成立。 I. L(r+s)=L(r)L(s), L(r)=L(rs0)L(r*s*), L(s)=L(r0s)L(r*s*) 那么L(r+s)=L(r)L(s) L(r*s*)，(L(r+s))* (L(r*s*))*, L((r+s)*) L( (r*s*)* ),所以(r+s)* (r*s*)* II. (r+s)*= ((r+s)*)*, 對任意m,n>=0,rmsn (r+s)m+n ，所以r*s*(r+s)* (r*s*)*((r+s)*)*= (r+s)* 由I，II可以知道(r*s*)*(r+s)*，(r+s)* (r*s*)* 得到(r+s)*=(r*s*)* (6)(r+s)*=r*+s* 不成立，假設r,s分別是表示語言R，S的正則表達式，例如當R={0}，S={1},L((r+s)*)={x| x=或者x是所有由0,1組成的字符串} L(r*+s*)=L(r*)L(s*)={,0,00,000,……}{,1,11,111,……} L((r+s)*) L(r*+s*),例如10 L((r+s)*),10 L(r*+s*) ********************************************************************************************** 5.構造下列正則表達式的等價FA 吳丹 02282090 ********************************************************************************* 6、構造等價于下圖所示DFA的正則表達式。 僅給出（2）的構造過程 （1） 與他等價的正則表達式為： ε+（01+1）（01+10+11（01+1））* S q1 q0 q2 q3 1 0 0 0 1 1 1 0 （2） 答案(之一)：( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (e+(1+00)((1+00*1)0)*00*) q1 q0 q2 q3 1 0 0 0 1 1 1 0 e e X Y e 預處理： 去掉q3： q1 q0 q2 1 0 1 1+00*1 0 e X Y e 00* 去掉q1： q0 q2 1+00 (1+00*1)0 e X Y e 00* (1+00*1)1 01 q0 e X Y e+(1+00)((1+00*1)0)*00* 01+(1+00)((1+00*1)0)*((1+00*1)1) 去掉q2： 去掉q0： X Y (01+(1+00)((1+00*1)0)*((1+00*1)1))* (e+(1+00)((1+00*1)0)*00*) （3） （（0+10）* 11）（01+(1+00）（0+10）* 11)*（0+（1+00）（0+10）*1）+（0+10）* 1 (4） （（0+11+10（0+1））（（01）*+（00（0+1））*）*1）*（1+10+ε+（0+11+10（0+1））（（01）*+（00（0+1）*）*）（00+0+ε）） ******************************************************************************************* 7.整理不同模型等價證明的思路 解：正則語言有5種等價的描述模型：正則文法（RG）、確定的有窮狀態(tài)自動機（DFA）、不確定的有窮狀態(tài)自動機（NFA）、帶空移動的有窮狀態(tài)自動機（）、正則表達式（RE）。這5種等價模型的轉(zhuǎn)換關系可以用下圖表示： （1） RG分為右線性文法和左線性文法。 對于右線性文法，只需要采用模擬M的移動即可 ， M的開始符號就是G的開始符號。 而對于左線性文法，G用規(guī)約模擬M的移動： 新增加的符號Z為G的識別符號，也就是開始符號。 （2） 同上，分為右線性和左線性文法。 對于右線性文法： 其中，G的開始符號為M的開始符號，新增的狀態(tài)Z為M的終止狀態(tài)。 對于左線性文法： 增加Z為M的開始狀態(tài)；對應形如的產(chǎn)生式，定義；對應形如的產(chǎn)生式，定義；G的開始符號為M的終止狀態(tài)。 （3） 采用圖上作業(yè)法： 預處理：標記X、Y的狀態(tài)為標記狀態(tài)，刪除不可達狀態(tài)； 并 ?。河脧膓到p的、標記為r1+r2……rg的弧取代q到p的標記為r1,r2……的并行弧。 去狀態(tài)：如果從q到p有一條標記為r1的弧，從p到t有一條標記為r2的弧，不存在從狀態(tài)p到狀態(tài)p的弧，將狀態(tài)p和與之關聯(lián)的這兩條弧去掉，用一條從q到t的標記為r1r2的弧代替；如果從q到p有一條標記為r1的弧，從p到t有一條標記為r2的弧，從狀態(tài)p到狀態(tài)p標記為r3的弧，將狀態(tài)p和與之關聯(lián)的這三條弧去掉，用一條從q到t的標記為r1r3*r2的弧代替；如果圖中只有三個狀態(tài)，而且不存在從標記為X的狀態(tài)到達標記為Y的狀態(tài)的路，則將除標記為X的狀態(tài)和標記為Y的狀態(tài)之外的第3個狀態(tài)及其相關的弧全部刪除。 處 理：從標記為X的狀態(tài)到標記為Y的狀態(tài)的弧的標記為所求的正則表達式。如果此弧不存在，則所求的正則表達式為Φ。 （4） 由于NFA也是一個特殊的，則其轉(zhuǎn)化可以參考 （5） （6）：確定化