形式語(yǔ)言與自動(dòng)機(jī)理論試題

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

2、+且x 的第十個(gè)字符為1(設(shè)置一個(gè)陷阱狀態(tài),一旦發(fā)現(xiàn)x 的第十個(gè)字符為0,進(jìn)入陷阱狀態(tài)1S0,10,10,10,10,110,0,10,10,10,10,1二、判斷(正確的寫T ,錯(cuò)誤的寫F 5x2'1.設(shè)1R 和2R 是集合a,b,c,d,e上的二元關(guān)系,則3231321(R R R R R R R ( T 任取(x.,y,其中x,y ,e d c b a ,使得321(,(R R R y x 。 ,(,(321R y z R R z x z ,e d c b a z ,(,(,(321R y z R z x R z x z ,(,(,(,(3231R y z R z x z R y

3、 z R z x z 3231,(,(R R y x R R y x 3231,(R R R R y x 2.對(duì)于任一非空集合A ,A2 ( T 3.文法G :S A|AS A a|b|c|d|e|f|g 是RG ( F 4.3型語(yǔ)言2型語(yǔ)言1型語(yǔ)言0型語(yǔ)言 ( F 5.s (rs+s *r=rr *s (rr *s * ( F 不成立,假設(shè)r,s 分別是表示語(yǔ)言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é)論不成立

4、三、設(shè)文法G 的產(chǎn)生式集如下,試給出句子aaabbbccc 的至少兩個(gè)不同的推導(dǎo)(12分。 aSBCaBC S | ab aB bB bb CB BC bC bc cC cc推導(dǎo)一: S=>aSBC=>aaSBCBC=>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC=>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc推導(dǎo)二:S=>aSBC=>aaSBCBC=>aaaBCBC

5、BC=>aaaBBCCBC =>aaaBBCBCC =>aaabBCBCC=>aaabbCBCC=>aaabbBCCC =>aaabbbCCC=>aaabbbcCC=>aaabbbccC=>aaabbbccc四、判斷語(yǔ)言n n n 010|n>=1是否為RL ,如果是,請(qǐng)構(gòu)造出它的有窮描述(FA,RG 或者RL ;如果不是,請(qǐng)證明你的結(jié)論(12分解:設(shè)L=nnn 010|n>=1。假設(shè)L 是RL ,則它滿足泵引理。不妨設(shè)N 是泵引理所指的僅依賴于 L 的正整數(shù),取Z=N N N 010 顯然,Z L 。按照泵引理所述,必存在u

6、,v ,w 。由于|uv|<=N,并且|v|>=1,所以v 只可能是由0組成的非空串。不妨設(shè)v=k0,k>=1 此時(shí)有u=jk N -0,w=NN j 010 從而有uv i w=NNj ikjk N 0100(0- 當(dāng)i=2時(shí),有uv 2w=NNkN 010+ 又因?yàn)閗>=1,所以 N+k>N 這就是說NNkN 010+不屬于L ,這與泵引理矛盾。所以,L 不是RL 。五、構(gòu)造等價(jià)于下圖所示DFA 的正則表達(dá)式。(12分答案(之一:( 01+(1+00(1+00*10*(1+00*11 * (+(1+00(1+00*10*00*Sq 1 q 0q 2q 310

7、111預(yù)處理:去掉q3:去掉q1:q1q0q2q310 01 1 1X Yq1q0q2111+00*1X Y00*q0q21+00(1+00*10XY00*(1+00*1101去掉q 2:去掉q 0:六、設(shè)M=(210,q q q ,0,1,0,1,B,0q ,B,2q ,其中的定義如下: (0q ,0=(0q ,0,R (0q ,1=(1q ,1,R (1q ,0=(1q ,0,R (1q ,B =(2q ,B ,R 請(qǐng)根據(jù)此定義,給出M 處理字符串00001000,10000的過程中ID 的變化。(10分 解:處理輸入串00001000的過程中經(jīng)歷的ID 變化序列如下: 0q0000100

8、000q0001000 000q001000 0000q 01000 00000q 10000 000011q00000000101q0000001001q000010001q00001000B 2q 處理輸入串10000的過程中經(jīng)歷的ID 變化序列如下: 0q 10000 11q 00000101q0001001q0010001q100001q 10000B 2q七、根據(jù)給定的NFA ,構(gòu)造與之等價(jià)的DFA 。(14分 NFA M 的狀態(tài)轉(zhuǎn)移函數(shù)如下表q 0XY+(1+00(1+00*10*00*01+(1+00(1+00*10*(1+00*11XY(01+(1+00(1+00*10*(1+

9、00*11* (+(1+00(1+00*10*00*解答:狀態(tài)說明狀態(tài)輸入字符1 2 開始狀態(tài)q0 q0,q1 q0,q2 q0,q2 q0,q1 q0,q1,q3 q0,q2 q0,q2 q0,q2 q0,q1 q0,q1,q2,q3 q0,q1,q2q0,q1,q2 q0,q1,q3 q0,q1,q2,q3 q0,q1,q2 終止?fàn)顟B(tài) q0,q1,q3 q0,q1,q2,q3 q0, q2,q3 q0,q2 終止?fàn)顟B(tài) q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1, q2終止?fàn)顟B(tài)q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1, q

10、2q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,1221,20210,11狀態(tài)說明 狀態(tài)輸入字符1 2 開始狀態(tài)q0 q0,q1 q0,q2q0,q2q1 q3,q0q2q2q3,q1 q2,q1 終止?fàn)顟B(tài) q3q3,q2q3 q0參 考 題 目1、設(shè),c b a =,構(gòu)造下列語(yǔ)言的文法。 (1 0|1=n b a L n n 。解答:,|,(1S aSb S b a S G =。 (2 1,|2=m n b a L m n 。解答:,|,|,|,(2S b bB B a aA A B A S b a B A S G =。 (3 1

11、|3=n a b a L n n n 。解答:,(33S P b a B A S G = :3P S aAB|aSAB BA AB aB ab bB bb bA ba aA aa(4 1,|4=k m n a b a L k m n 。解答:,|,|,(4S b bB B a aA A ABA S b a A S G =。(5 ,|5+=w a awa L 。解答:,|,(5S c b a cW bW aW W aWa S c b a W S G =。 (6 ,|6+=w x xwxL T。解答:,(66S P c b a W S G = :6P c W c b W b a W a S | c

12、 b a cW bW aW W |。(7 ,|7+=w w w w L T 。解答:,|,7S c b a cWc bWb aWa S c b a W S G =。(8 ,|8+=w x w xx L T 。解答:,(88S P c b a X W S G = XW S P :8c b a c X c b X b a X a X | c b a cW bW aW W |。2、給定RG :11111(,G V T P S =,2222,2(,G V T P S =,試分別構(gòu)造滿足下列要求的RG G ,并證明你的結(jié)論。12(1(L G L G L G =(1212121212332111*1212

13、2121111*2222 V V S V V G S VV T T P P P S P S S T S S S S x L G S xx L G L G L G L G x S S x x x x T x L G S x G P x L += 解:不妨假設(shè),并且,令,其中,且證明:(1設(shè),則若,因?yàn)?所以成立若,由產(chǎn)生式,不妨設(shè),其中,則,因?yàn)榈漠a(chǎn)生式包括,所以(2121212*1212111122221321112121212*1312*2221 G x x x L G L G L G L G L G x L G L G x x x x T S x x T S x x P S S T S S

14、 x S x x x x L G L G L G L G x P S S S x x S S x x L G L G L G +=,可知所以 (1設(shè),不妨設(shè),其中,時(shí),由中且,則所以,時(shí),由中時(shí),由,得所以(212L G L G L G L G =綜上,12(2(L G L G L G =(12121212123312*1211*12*312*111 V V S V V G S VV T T P P P S P S S S x L G L G x L G S xG S x x L G L G L G L G x L G S x P S x S xS x x L G L G L G = 解:不妨

15、假設(shè),并且,令,其中,或證明:(1設(shè)不妨設(shè)那么可知由構(gòu)造方法可知,且即(2設(shè)則,由知,或不妨設(shè)則,同理(21212 L G L G L G L G L G L G L G L G = 則 所以12(3(,(,L G L G a b L G a =其中,b 是兩個(gè)不同的終極符號(hào)(12121212123*322111*212*112211*(,( (V V S V V G S VV T T P P P S P S aS bS T S S S x L G S x S aS x a T S L G L G x a L G a b L G b L G = 解:不妨假設(shè),并且,令,其中,其中且證明:(1設(shè)

16、則由產(chǎn)生式,不妨設(shè)則,則,所以同理(21212*1211221122*312121212,(,( (,( (,( (,(a b L G L G L G a b L G x L G a b L G x a L G L G S S P S aS a L G a b L G L G L G L G a b L G =可得(2設(shè)不妨設(shè)其中,即, 由中產(chǎn)生式 所以綜上可得,*1(4(L G L G =解: P=S |S1P1S S S|S1P1 證明略。1(5(L G L G +=解: P=S |S1P1S S|S1P1 證明略。3、設(shè)文法G 有如下產(chǎn)生式: S aB bAA a aS bAAB b b

17、S aBB證明L(G=中含有相同個(gè)數(shù)的a 和b ,且非空。證:觀察發(fā)現(xiàn)A 的產(chǎn)生式A bAA 中的bA 可以用S 來代替,同樣B 的產(chǎn)生式B aBB 中的aB 也可以用S 代替。這樣原來的文法可以化為如下的形式: S aB bAA a aS SAB b bS SB進(jìn)一步地,可以把產(chǎn)生式A aS 中的S 代換,把文法化為如下的形式: S aB bAA a aaB abA SA B b baB bbA SB7.設(shè)DFA M=,(0F q Q ,證明:對(duì)于=,(,(,*y x q xy q Q q y x 注:采用歸納證明的思路證明: (周期律 02282067 首先對(duì)y 歸納,對(duì)任意x 來說,|y

18、| = 0時(shí),即y=根據(jù)DFA 定義,(q q =,(,(,(,(y x q x q x q xy q =,故原式成立。當(dāng)|y| = n 時(shí),假設(shè)原式成立,故當(dāng)|y|= n+1時(shí), 不妨設(shè)y = wa, |w| = n, |a| = 1根據(jù)DFA 定義=a a x q xa q ,(,(,故,(,(,(,(,(,(y x q wa x q a w x q a xw q xwa q xy q =原式成立,同理可證,對(duì)任意的y 來說,結(jié)論也是成立的。綜上所述,原式得證*8.證明:對(duì)于任意的DFA M 1=(Q,q 0,F 1 存在DFA M 2=(Q,q 0,F 2, 使得L(M 2=*L (M

19、1。 證明:(1構(gòu)造M 2。 設(shè)DFA M 1=(Q,q 0,F 1 取DFA M 2=(Q,q 0,Q F 1 (2證明L(M 2=*L (M 1對(duì)任意x *x L(M 2=*L (M 1(q,xQ F 1(q,x Q 并且(q,x F 1x *并且x L(M 1x *L (M 110、構(gòu)造識(shí)別下列語(yǔ)言的NFA(10,100x x x +且中不含形如的子串1101011S(20,110110x x x +且中含形如的子串10110,10,1(30,1x x x +且中不含形如10110的子串10110,10,1(40,110101x x x +和的倒數(shù)第個(gè)字符是,且以結(jié)尾0,110,10,1

20、0,10,10,100,110,1(50,101x x x +且以開頭以結(jié)尾010,1(60,1x x x +且中至少含有兩個(gè)1S0,1110,10,10,1*(70,1x x x 且如果以1結(jié)尾,則它的長(zhǎng)度為偶數(shù);如果以0結(jié)尾,則它的長(zhǎng)度為奇數(shù)S10,1(80,1x x x +且的首字符和尾字符相等00,10,100111(9,0,1Tx xx +0,100110,111.根據(jù)給定的NFA ,構(gòu)造與之等價(jià)的DFA . (1 NFA M 1 的狀態(tài)轉(zhuǎn)移函數(shù)如表3-9 狀態(tài)說明狀態(tài)輸入字符1 2 開始狀態(tài)q0 q0,q1 q0,q2q0,q2q1 q3,q0q2q2 q3,q1q2,q1 終止?fàn)?/p>

21、態(tài) q3 q3,q2 q3 q0解答:狀態(tài)說明狀態(tài)輸入字符1 2 開始狀態(tài)q0 q0,q1 q0,q2 q0,q2 q0,q1 q0,q1,q3 q0,q2 q0,q2 q0,q2 q0,q1 q0,q1,q2,q3 q0,q1,q2q0,q1,q2 q0,q1,q3 q0,q1,q2,q3 q0,q1,q2 終止?fàn)顟B(tài) q0,q1,q3 q0,q1,q2,q3 q0, q2,q3 q0,q1,q2 終止?fàn)顟B(tài) q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0, q2終止?fàn)顟B(tài)q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1, q2q0q0,q1q0

22、,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,1221,20210,11圖3-9所示NFA 等價(jià)的DFA13.試給出一個(gè)構(gòu)造方法,對(duì)于任意的NFA ,(10111F q Q M =,構(gòu)造NFA =2M,(2022F q Q ,使得(1*2M L M L -=注:轉(zhuǎn)化成相應(yīng)的DFA 進(jìn)行處理,然后可參考第8題的思路證明:首先構(gòu)造一個(gè)與NFA 1M 等價(jià)的DFA ,3M 根據(jù)定理3.1(P106,(13M L M L = 構(gòu)造,(30333F q Q M =其中=a Q p p p F p p p Q p p p p p p F Q m m m m Q

23、,.,.,.,|.,2211212121331 .,.(.,.(111113m n m n p p a q q p p a q q =在此基礎(chǔ)上2M ,3232=Q Q .|.3112=F p p p p F m m 即取所有1M 確定化后不是終結(jié)狀態(tài)的狀態(tài)為2M 的終結(jié)狀態(tài)。 為了證明(3*2M L M L -=,我們?cè)?M 的基礎(chǔ)上=4M,(4044F q Q ,其中,3434=Q Q 44Q F =,即所有1M 確定化后的狀態(tài)都為終結(jié)狀態(tài)。顯然,(*4=M L,(2M L x 則20,(F x q ,(,(330M L x F x q 又因?yàn)?(,(,(04030x q F x q Q

24、x q ,(*4=M L 故x (3*M L -,故(3*2M L M L -同理容易證明(3*2M L M L -故(3*2M L M L -=,又因?yàn)?13M L M L =,故(1*2M L M L -=可知,構(gòu)造的2M 是符合要求的。15.P129 15.(1、(2(1根據(jù)NFAM 3的狀態(tài)轉(zhuǎn)移函數(shù),起始狀態(tài)q 0的閉包為 -CLOSURE (q 0= q 0, q 2。由此對(duì)以后每輸入一個(gè)字符后得到的新狀態(tài)再做閉包,得到下表: (陶文婧 02282085 狀態(tài) 01 q 0, q 2 q 0, q 1,q 2 q 0, q 1,q 2,q 3 q 0, q 1,q 2 q 0, q

25、1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3q 0= q 0, q 2,q 1= q 0, q 1,q 2,q 2= q 0, q 1,q 2,q 3,因?yàn)閝 3為終止?fàn)顟B(tài),所以q 2= q 0, q 1,q 2,q 3為終止?fàn)顟B(tài)Sq 1q 2q 000,10,1(2用上述方法得 狀態(tài) 01 q 1, q 3 q 3,q 2 q 0, q 1,q 2,q 3 q 3,q 2 q 3,q 2 q 0, q 1,q 3 q 0, q 1,q 2,q 3 q 1,q 2,q 3 q 0, q

26、 1,q 2,q 3 q 0, q 1,q 3 q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 1,q 2,q 3 q 3,q 2 q 0, q 1,q 2,q 3q 0= q 1, q 3,q 1= q 3,q 2,q 2= q 0, q 1,q 2,q 3,q 3= q 0, q 1,q 3,q 4= q 1,q 2,q 3因?yàn)楦鳡顟B(tài)均含有終止?fàn)顟B(tài),所以q 0, q 1,q 2,q 3,q 4均為終止?fàn)顟B(tài)1Sq 1q 2q 0q 4q 310011注:本題沒有必要按照NFA 到DFA 轉(zhuǎn)化的方法來做,而且從-NFA 到NFA 轉(zhuǎn)化時(shí)狀態(tài)沒有必要改變,可以完全采用-NFA 中的

27、狀態(tài)如(1狀態(tài)0 1q0(開始狀態(tài) q0, q1,q2 q3 q0, q1,q2,q3q1 q0, q1,q2,q3 q1,q2,q3q2 q0, q1,q2,q3 q1,q2,q3q3(終止?fàn)顟B(tài) q0, q1,q2,q3 q0, q1,q2,q3(2狀態(tài)0 1q0(開始狀態(tài) q1 q2q3, q0, q1,q2,q3q1 q2 q1,q2q2,q2,q3 q0, q2,q3q3(終止?fàn)顟B(tài)空 q0 16、證明對(duì)于的FA M1=(Q1,1,1,q01,F1,FA M1=(Q2,2,2,q02,F2,存在FA M,使得L(M= L(M1L(M2證明:不妨設(shè)Q1 與Q2的交集為空(1構(gòu)造M=(Q1Q

28、2 q0, q0,F其中:1=12 F= F1F22 (q0,= q01 ,q02 對(duì)于 qQ1,a1(q, a=1(q,a對(duì)于 qQ2,a2 ,(q, a=2(q,a(1證明:1首先證L(M1L(M2L(M設(shè)x L(M1L(M2,從而有x L(M1或者x L(M2,當(dāng)x L(M1時(shí)1(q01,xF1由M的定義可得:(q0,x=(q0,x=(q0, x=(q01 ,q02,x=(q01 , x(q02, x=1(q01 , x (q01 , xF1(q01 , x 即xL(M同理可證當(dāng)x L(M2時(shí)xL(M故L(M1L(M2L(M2 再證明L(ML(M 1L(M 2設(shè)x L(M 則(q 0,x

29、 F 由M 的定義:(q 0,x =(q 0,x =(q 0, x=(q 01 ,q 02,x =(q 01 , x(q 02, x 如果是(q 01 , x 因?yàn)镼 1 與Q 2的交集為空 而且(q 0,x F F= F 1F 2 則 (q 01 , x= 1(q 01 , xF 1 因此x L(M 1如果是(q 02 , x 因?yàn)镼 1 與Q 2的交集為空 而且(q 0,x F F= F 1F 2 則 (q 02 , x= 2(q 02 , xF 1 因此x L(M 2因此x L(M 1L(M 2 L(ML(M 1L(M 2得證 因此L(M= L(M 1L(M 217 證明:對(duì)于任意的FA

30、 ,(,(20222221011111F q Q FAMF q Q M =L(M L(M L(MM,FA 21=使得存在.證明:令 ,其中的定義為: 1 對(duì)q Q 1-f 1,a (q ,a=1(q ,a;2 對(duì)q Q 2-f 2,a (q ,a=2(q ,a; 3 (f 1,=q 02 要證 , 只需證明 ,1. 證明,(20121f q Q Q M = (21M L M L ML =(21M L M L M L (21M L M L M L 21221121,(,(x x x M L x M L x M L M L x =使得并且從而有設(shè),(,(,(,(,1201110111111f x

31、q x q a q x q a Q q M Q x M =故對(duì)時(shí)所以在定義中的狀態(tài)經(jīng)過的狀態(tài)全部都是的過程中在處理(,(,(,(,(,20122021222M L x f x q x q a q x q a Q q M Q x M =下面證明對(duì)時(shí)所以在定義中的狀態(tài)經(jīng)過的狀態(tài)全部都是的過程中在處理(21M L M L M L 2 再證明(,(,(,(,(,(,(,(,(,(22022202212121210112101210101MLxfxqxqxfxfxfxxqxxqxxqxq=即得證,(,(;,(,(,(,(,(,(,(.,x,xxx,xxx,(.,(,/p>

32、2202212121010120221011212121021120120121fxqfxqfxqfxqfxqxfxfxxqxqfqMxfqMffqfffMMqMfxqMLxMLMLML=說明說明其中即引導(dǎo)到狀態(tài)從狀態(tài)將引導(dǎo)到狀態(tài)從狀態(tài)將并且使得和后綴的前綴比存在所以移動(dòng)的必經(jīng)而且該移動(dòng)是出發(fā)的任何其他移動(dòng)不存在從外的移動(dòng)函數(shù)式由于除了對(duì)應(yīng)狀態(tài)轉(zhuǎn)移先到必須要達(dá)到狀態(tài)的定義可知由啟動(dòng)的是從由于即設(shè)212121212211(,(ML M L M L M L M L M L M L M L x x x M L x M L x =綜上所述故從而這表明* (吳丹 02282090(11110112202212121201121218.FA M Q q F FA M Q q F FA M L M L M L M FA D FAM Q Q q q F a Q ,q,p a q a p a