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

2、一個陷阱狀態(tài),一旦發(fā)現(xiàn)x 的第十個字符為0,進入陷阱狀態(tài)1S0,10,10,10,10,110,0,10,10,10,10,1二、判斷(正確的寫T ,錯誤的寫F 5x21.設(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 z R z x z 3231,(,(R

3、 R y x R R y x 3231,(R R R R y x 2.對于任一非空集合A ,A2 ( T 3.文法G :S A|AS A a|b|c|d|e|f|g 是RG ( F 4.3型語言2型語言1型語言0型語言 ( F 5.s (rs+s *r=rr *s (rr *s * ( F 不成立,假設(shè)r,s 分別是表示語言R ,S 的正則表達式,例如當(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)生式集如下,試給出句子

4、aaabbbccc 的至少兩個不同的推導(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=aaaBCBCBC=aaaBBCCBC =aaaBBCBCC =aaabBCBCC=aaabbCBCC=aaabbBCCC =aaabbbCCC=aaabbbcCC=aaab

5、bbccC=aaabbbccc四、判斷語言n n n 010|n=1是否為RL ,如果是,請構(gòu)造出它的有窮描述(FA,RG 或者RL ;如果不是,請證明你的結(jié)論(12分解:設(shè)L=nnn 010|n=1。假設(shè)L 是RL ,則它滿足泵引理。不妨設(shè)N 是泵引理所指的僅依賴于 L 的正整數(shù),取Z=N N N 010 顯然,Z L 。按照泵引理所述,必存在u ,v ,w 。由于|uv|=1,所以v 只可能是由0組成的非空串。不妨設(shè)v=k0,k=1 此時有u=jk N -0,w=NN j 010 從而有uv i w=NNj ikjk N 0100(0- 當(dāng)i=2時,有uv 2w=NNkN 010+ 又因為

6、k=1,所以 N+kN 這就是說NNkN 010+不屬于L ,這與泵引理矛盾。所以,L 不是RL 。五、構(gòu)造等價于下圖所示DFA 的正則表達式。(12分答案(之一:( 01+(1+00(1+00*10*(1+00*11 * (+(1+00(1+00*10*00*Sq 1 q 0q 2q 310 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

7、=(0q ,0,R (0q ,1=(1q ,1,R (1q ,0=(1q ,0,R (1q ,B =(2q ,B ,R 請根據(jù)此定義,給出M 處理字符串00001000,10000的過程中ID 的變化。(10分 解:處理輸入串00001000的過程中經(jīng)歷的ID 變化序列如下: 0q0000100000q0001000 000q001000 0000q 01000 00000q 10000 000011q00000000101q0000001001q000010001q00001000B 2q 處理輸入串10000的過程中經(jīng)歷的ID 變化序列如下: 0q 10000 11q 00000101q0

8、001001q0010001q100001q 10000B 2q七、根據(jù)給定的NFA ,構(gòu)造與之等價的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+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,q

9、2,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, q2q0q0,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參 考 題

10、 目1、設(shè),c b a =,構(gòu)造下列語言的文法。 (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|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

11、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 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

12、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*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è),則若,因為,所以成立若,由產(chǎn)生式,不妨

13、設(shè),其中,則,因為的產(chǎn)生式包括,所以(2121212*1321112121212*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 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è),其中,時,由中且,則所以,時,由中時,由,得所以(212L G L G L G L G =綜上,12(2(L G L G L G =(12121212123312*1211*12*312*111

14、 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 = 解:不妨假設(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 是兩個不同的終極符號(12121212123*322111*212*112211*(,( (V

15、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è)則由產(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)生式

16、所以綜上可得,*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 bS aBB證明L(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進一步地,可以把產(chǎn)生式A aS 中的S 代換,把文法化為如下的形式: S aB bAA

17、a aaB abA SA B b baB bbA SB7.設(shè)DFA M=,(0F q Q ,證明:對于=,(,(,*y x q xy q Q q y x 注:采用歸納證明的思路證明: (周期律 02282067 首先對y 歸納,對任意x 來說,|y| = 0時,即y=根據(jù)DFA 定義,(q q =,(,(,(,(y x q x q x q xy q =,故原式成立。當(dāng)|y| = n 時,假設(shè)原式成立,故當(dāng)|y|= n+1時, 不妨設(shè)y = wa, |w| = n, |a| = 1根據(jù)DFA 定義=a a x q xa q ,(,(,故,(,(,(,(,(,(y x q wa x q a w x

18、 q a xw q xwa q xy q =原式成立,同理可證,對任意的y 來說,結(jié)論也是成立的。綜上所述,原式得證*8.證明:對于任意的DFA M 1=(Q,q 0,F 1 存在DFA M 2=(Q,q 0,F 2, 使得L(M 2=*L (M 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對任意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)造識別下列語言的NFA(10,100x x x +且中不含形

19、如的子串1101011S(20,110110x x x +且中含形如的子串10110,10,1(30,1x x x +且中不含形如10110的子串10110,10,1(40,110101x x x +和的倒數(shù)第個字符是,且以結(jié)尾0,110,10,10,10,10,100,110,1(50,101x x x +且以開頭以結(jié)尾010,1(60,1x x x +且中至少含有兩個1S0,1110,10,10,1*(70,1x x x 且如果以1結(jié)尾,則它的長度為偶數(shù);如果以0結(jié)尾,則它的長度為奇數(shù)S10,1(80,1x x x +且的首字符和尾字符相等00,10,100111(9,0,1Tx xx +

20、0,100110,111.根據(jù)給定的NFA ,構(gòu)造與之等價的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)顟B(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,

21、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,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,1221,20210,11圖3-9所示NFA 等價的DFA13.試給出一個構(gòu)造方法,對于任意的NFA ,(10111F q Q M =,構(gòu)造NFA =2M,(2022F q Q ,使得(1*2M L M L -=注:轉(zhuǎn)化成相應(yīng)的DFA 進行處理,然后可參考第8題

22、的思路證明:首先構(gòu)造一個與NFA 1M 等價的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 ,.,.,.,|.,2 .,.(.,.(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 -=,我們在3M 的基礎(chǔ)上=4M,(4044F q Q ,其中,

23、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 又因為,(,(,(04030x q F x q Q x q ,(*4=M L 故x (3*M L -,故(3*2M L M L -同理容易證明(3*2M L M L -故(3*2M L M L -=,又因為(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

24、 2。由此對以后每輸入一個字符后得到的新狀態(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 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,因為q 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(

25、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 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因為各狀態(tài)均含有終止?fàn)顟B(tài),所以q

26、 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)化時狀態(tài)沒有必要改變,可以完全采用-NFA 中的狀態(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,q

27、3q3(終止?fàn)顟B(tài)空 q0 16、證明對于的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=(Q1Q2 q0, q0,F其中:1=12 F= F1F22 (q0,= q01 ,q02 對于 qQ1,a1(q, a=1(q,a對于 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時1(q01,xF1由M的定義可得:(q0,x=(q0,x=(q0, x=(q01 ,q02,

28、x=(q01 , x(q02, x=1(q01 , x (q01 , xF1(q01 , x 即xL(M同理可證當(dāng)x L(M2時xL(M故L(M1L(M2L(M2 再證明L(ML(M 1L(M 2設(shè)x L(M 則(q 0,x 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 因為Q 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 因為Q 1 與Q 2的交集為空 而且(q 0

29、,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 證明:對于任意的FA ,(,(20222221011111F q Q FAMF q Q M =L(M L(M L(MM,FA 21=使得存在.證明:令 ,其中的定義為: 1 對q Q 1-f 1,a (q ,a=1(q ,a;2 對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

30、 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è)中的狀態(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 =下面證明對時所以在定義中的狀態(tài)經(jīng)過的狀態(tài)全部都是的過程中在處理(21M L M L M L 2 再證明(,(,(,(,(,(,(,(,(,(22022202212121210112101210101MLxfxqxqxfxfxfxxqxxqxxqxq=即得證,(,(;,

31、(,(,(,(,(,(,(.,x,xxx,xxx,(.,(,(2202222021101111012202212121010120221011212121021120120121fxqfxqfxqfxqfxqxfxfxxqxqfqMxfqMffqfffMMqMfxqMLxMLMLML=說明說明其中即引導(dǎo)到狀態(tài)從狀態(tài)將引導(dǎo)到狀態(tài)從狀態(tài)將并且使得和后綴的前綴比存在所以移動的必經(jīng)而且該移動是出發(fā)的任何其他移動不存在從外的移動函數(shù)式由于除了對應(yīng)狀態(tài)轉(zhuǎn)移先到必須要達到狀態(tài)的定義可知由啟動的是從由于即設(shè)2(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(218.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 .x L M 1 2.1,x x x xk xi i k