形式語言與自動(dòng)機(jī)理論試題答案解析

1、 / 6形式語言與自動(dòng)機(jī)理論試題答案解析一、按要求完成下列填空.給出集合,和集合 & ,0,00的募集(2x4),，, e ,0,00,8 ,0, 8 ,00,0,00, e ,0,00.設(shè)=0,1,請(qǐng)給出工上的下列語言的文法(2x5)(1)所有包含子串01011的串S-X01011YXfe |0X|1X |0Y|1Y2)所有既沒有一對(duì)連續(xù)的0,也沒有一對(duì)連續(xù)的1的串A-e |A|A A - 0|01|01A A” - 1|10|10A”.構(gòu)造識(shí)別下列語言的DFA 2x6 x|x0, 1+且x以0開頭以1結(jié)尾(設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài))Sx|x 0, 1+且x的第十個(gè)字符

2、為1(設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個(gè)字符為0,進(jìn)入陷阱狀態(tài))、判斷(正確的寫T,錯(cuò)誤的寫F)5x2上的二元關(guān)系，則. 設(shè) Ri 和 R2 是集合a,b,c,d,e(R R)R RR3 RR任取(x.,y),其中 x,y a,b,c,d,e,使得(x, y) (RRz)R3。z(x,z) Ri R2 (z, y) RJ z a,b,c,d,ez(x, z)Ri(x,z) R2(z, y)R3)z(x, z)Ri(z,y)R3)z(x,z) R2 (z, y) R3)(x,y) RiR3 (x, y) R2R3(x, y) RiR3R2R3.對(duì)于任一非空集合A,2A( T ).文法 G: S

3、 tA|ASA a|b|c|d|e|f|g是 RG ( F ).3 型語言 2型語言 1型語言 0型語言 (F ).s(rs+s) *r=rr *s (rr *s) *( f )不成立，假設(shè)r,s分別是表示語言 R,S的正則表達(dá)式，例如當(dāng)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)*,結(jié)論不成立三、設(shè)文法G的產(chǎn)生式集如下，試給出句子aaabbbccc的至少兩個(gè)不 同的推導(dǎo)(12分)。S aBC | aSBCaB abbB

4、bbCB BCbC bccC cc推導(dǎo)一：S=aSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccC=aaabbbccc推導(dǎo)二：S=aSBC=aaSBCBC=aaaBCBCBC=aaaBBCCBC=aaaBBCBCC=aaabBCBCC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccC=aaabbbccc四、判斷語言0可0“門=1是否為RL,如果是，請(qǐng)構(gòu)造出它的有窮描述（FA,RG或者RL）;如果

5、不是，請(qǐng)證明你的結(jié)論（12分）解：設(shè)L= On1nOn|n=10假設(shè)L是RL,則它滿足泵引理。不妨設(shè) N是泵引理所指的僅依賴于L的正整數(shù)，取Z=0N1N0N 顯然，ZL o按照泵引理所述，必存在u, v, Wo由于|uv|v二N,并且所以v只可能是由。組成的非空用。不妨設(shè)v= 0k , k=1 此時(shí)有u=0N k j , w=0j1N0N 從而有 UViW=0N k （ObblNoN 當(dāng) j=2 時(shí)，有 uv 2 w= 0N klN0N 又因?yàn)?k=1）所以 N+kN 這就是說0N k1N0N不屬于L,這與泵引理矛盾。所以，L不是RL。五、構(gòu)造等價(jià)于下圖所示 DFA勺正則表達(dá)式。（12分）q2

6、0答案(之一) (+(1+00)(1+00*1)0)*00*)預(yù)處理：xT (q2去掉q3：.qq3:(01+(1+00)(1+00*1)0)*(1+00*1)1)*;Y q31.XT 0上q2去掉qX1+007 /b。* j (1+00*1)1 /4 / 600*(1+00*1)0q2 / 6+(1+00)(1+00*1)0)*00*去掉q2：q001+(1+00)(1+00*1)0)*(1+00*1)1)去掉q0：(01+(1+00)(1+00*1)0)*(1+00*1)1)* ( +(1+00)(1+00*1)0)*00*)六、設(shè) M= (50。, 0,1 , 0,1 , B, 匕 q,

7、B, Q),其中 S的定義如下：s(% 0)= (cb, 0, R)8 y, 1) = (q, 1, R)s (q, 0) = (q, 0, R)S (q, B) = B, R)請(qǐng)根據(jù)此定義，給出 M處理字符串00001000,10000的過程中ID的變化。(10分)解：處理輸入用00001000的過程中經(jīng)歷的ID變化序列如下:q0000010000 q00001000 1 m|00 q0001000000 q001000 1Ml 0000 q0 10000卜100001 q10000000010 q100 卜 0000100 q101 00001000q11 00001000Bq2處理輸入用

8、10000的過程中經(jīng)歷的ID變化序列如下:q010000卜I 1 q100000Kr10 q1000100 q1 00卜1000 q100000 q10000Bq2七、根據(jù)給定的NFA構(gòu)造與之等價(jià)的DFA （14分）NFA M勺狀態(tài)轉(zhuǎn)移函數(shù)如下表狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)q0q0,q1q0,q2q0,q2qiq3,q0q2q2q3,q1q2,q1終止?fàn)顟B(tài)q3q3,q2q3 q0解答:狀態(tài)說明狀態(tài)輸入字符012開始狀態(tài)qoq0,q1q0,q2q0,q2q0,q1q0,q1,q3q0,q2q0,q2q0，q2q0,q1q0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2終