形式语言与自动机理论精彩试题

1、标准文案形式语言与自动机理论试题、按要求完成下列填空1） 给出集合,和集合 £ ,0,00的募集 （2x4 ），2） ） ， e ,0,00,£ ,0, s ,00,0,00, s ,0,00一 一一 '、2. 设汇=0,1,请给出汇上的下列语言的文法（2x5 ）所有包含子串 01011的串S 一 X01011YX一 £ |0X|1XY一 e|0Y|1Y(2)所有既没有一对连续的0,也没有一对连续的1的串A 一 e |A' |A"A' 一 0101101A 'A” 一 1110110A ”、.一 '3. 构造识别下

2、列语百的DFA 2x6(1) x|x 0, 1+且x以0开头以1结尾(设置陷阱状态，当第一个字符为 1时，进入陷阱状态)(2) x|x 0, 1+且x的第十个字符为1(设置一个陷阱状态，一旦发现x的第十个字符为0,进入陷阱状态)0,1大全标准文案、判断(正确的写 T,错误的写F)5x21.设R和R2是集合a,b,c,d,e元关系，则(R R2)R3RR3R2R3(T)任取(x.,y),其中x,ya,b, c,d,e,使得(x, y)(Ri R2)R3。2.3.4.35.sz(x, z)z(x, z)z(x, z)(x, y)(x, y)对于任一非空集合 A,文法 G: S f|AS A型语言

3、2型语言RiRiRiRiR3RiR3R2(z, y)R3)za,b,c,d,e(x, z)(z, y)(x, y)R2R32aa|b|c|d|e|f|gi型语言(rs+s ) r=rr s (rr s)不成立，假设 r,s分别是表示语言L(s(rs+s)*r)L(rr*s(rr*s)*) 所以 s(rs+s)*rR2 (z, y)R3)z(x,z)R2(z, y)R3)R2R3(T )是 RG ( F )0型语言R, S的正则表达式，例如当是以i开头的字符串，而L(rr*s(rr*s)*) 是以0开头的字符串rr*s(rr*s)*,结论不成立R=0, S=i, .L(s(rs+s)*r)三、设

4、文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导(i2分)。S aBC|aSBCaB abbB 一 bbCB f BCbC 一 bccC 一 cc推导一：S=>aSBC=>aaSBCBC=>aaaBCBCBC=>aaabCBCBC=>aaabBCCBC=>aaabbCCBC大全标准文案=>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc推导二：S=>aSBC=>aaSBCBC=>aaaBCBCB

5、C=>aaaBBCCBC=>aaaBBCBCC=>aaabBCBCC =>aaabbCBCC=>aaabbBCCC =>aaabbbCCC =>aaabbbcCC=>aaabbbccC=>aaabbbccc四、判断语言 0n1n0n|n>=1是否为RL,如果是，请构造出它的有穷描述（FA,RG或者RL）;如果不是，请证明你的结论（12分）解：设L= 0n1n0n|n>=1。假设L是RL,则它满足泵引理。不妨设N是泵引理所指的仅依赖于L的正整数，取Z=0N1N0N显然，ZCL。按照泵引理所述，必存在 u, v, w。由于|uv|&

6、lt;二N,并且|v|>=1 ,所以v只可能是由0组成 的非空串。不妨设v=0k, k>=1 此时有u=0Nkj , w=0j1N0N从而有uviw=0N k j（0k）i0j1N0N 当 i=2 时，有 uv2w=0N k1N0N 又因为 k>=1,所以N+k>N这就是说0N k1N0N不属于L,这与泵引理矛盾。所以， L不是RL。五、构造等价于下图所示DFA的正则表达式。（12分）标准文案)*答 案 (之 一)：(01+(1+00)(1+00*1)0)*(1+00*1)1)(+(1+00)(1+00*1)0)*00*)去掉q3：q2去掉qi：大全标准文案去掉q2：0

7、1+(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*)六、设 m=( q0,q1,q2, 0,1 , 0,1 , b, s, C0,b, Q),其中 s的定义如下:M 0), 0) = (Cfc, 0, R)s( “，1)= (q，1, R)s( q, 0)=( q, 0, R)s( q, b) = a，b, R)请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分）解：处理输入串 00001000的过程中经历的ID变化序列如下：&q

8、uot;000010000 q0000100000 q00010001 ' 000 q0010000000 q010000卜M 00001 q1 0000000010 q1 000000100 q10U:l00001000q11 M100001000Bq2处理输入串10000的过程中经历的ID变化序列如下:q0100001 q1 0000010 q1000hi100 q1 00' 1000 q10'10000 q1.10000Bq2大全标准文案七、根据给定的 NFA构造与之等价的 DFA （14分） NFA M的状态转移函数如下表q0q0,q1,q3"1q0,

9、q2,q3大全q0,q2q0,q1,q2一一一200，10,1 q0,q1,q2,q32状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,q1q2,q1终止状态q3q3,q2q3 q0解答:状态说明状态输入字符012开始状态q0q0,q1q0，q2q0,q2q0,q1q0,q1,q3q0,q2q0,q2q0,q2q0,q1q0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2终止状态q0,q1,q3q0,q1,q2,q3q0, q2,q3q0,q2终止状态q0,q2,q3q0,q1,q2,q3q

10、0,q1,q2,q3q0,q1, q2终止状态q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1, q2标准文案参考题目1、 a,b,c, ，构造下列语言的文法。(1) L1 anbn |n 0。解答： G1( S, a,b,S aSb| , S) 。(2) L2 anbm | n,m 1 。解答： G2 (S,A,B, a,b, S A| B,A aA|a,B bB | b, S) 。(3) L3 anbnan |n 1。解答： G3(S,A, B, a,b, P3,S)P3: S faAB|aSABBA fAB aB f ab bB f bb bA fba aA

11、f aa(4) L4 anbmak | n, m,k 1 。解答：G4 (S, A, a,b, S ABA, AaA|a, B bB | b, S)。(5) L5 awa | a ,w 。解答：G5 ( S,W, a,b,c,S aWa,W aW | bW |cW | a |b| c, S) 。(6) L6 xwxT | x, w 。解答： G6 (S,W,a,b,c, P6,S)P6: SaWa | bWb | cWcW aW | bW | cW | a | b | c。(7) L7 w|w wT,w。解答： G7 S,W, a,b,c, S aWa |bWb |cWc |a | b |c,

12、 S 。大全标准文案(8) L8 xxTw|x,w。解答：G8(S,W,X, a,b,c, P8，S)P8 : SXWX aXa | bXb | cXc |a | b |cW aW |bW | cW | a |b | c。2、给定RG Gi (5工上，) , G2 (V2,T2,P2§2),试分别构造满足下列要求的RG G并证明你的结论。(1)L(G) L(Gi)L(G2)解：不妨假设MI v2,并且S V1UV2,令G S UV1UV2,1 UT2, P U P2 UP3, S其中，P5ss21且 s U SSiU S证明：、一 *(1)设x L G ,则S x若x，因为 L G

13、, L G2 ,所以 L G1 L G2成立若x,由产生式SS2,不妨设xx1x2,其中x1T1,x1L G1则S2*x2,因为G的产生式包括F2,所以x2LG2,可知xx1x2LG1L G2所以 LG L G L G2*-r-*(1)设 xLG1 L G2,不妨设 x x1x2,其中 x1 T1 , §x1, x2T2, S2x2xi 时，由B 中 SS2 Ti 且 § ，则 S x1s2 xix2所以 x1x2 L G , L G1 L G2L Gx1 时，由"中 S |S1S * x2x2时，由S ,得Sx2所以x2 L GL Gi L G2 L G综上，L

14、G L Gi L G2 L(G) L(Gi)UL(G2)大全标准文案解：不妨假设 V1I V2,并且S V1 UV2,令G S UV1 UV2, T1UT2, RUP2UP3, S其中，P3 SSi或 S2证明：(1)设x L G1 UL G2 不妨设x L G1 那么可知蚪 *x由G构造万法可知， S x且x L G 即L G1 UL G2 L G(2)设x L G 则Sx,由 P3知，Six或S2x不妨设 S1x 则 x L G1 , L G1L G同理 L G2 L G 则 L G1 UL G2 L G所以 LG L G1 UL G2(3)L(G) L(Gi) a,b L(Gz),其中a

15、, b是两个不同的终极符号解：不妨假设 V11V2,并且S V1 UV2,令G S UV1 UV2, T1UT2, RUp2UP3, SP3SaS2 bS2 其中Ti* 且 Si *证明：(i)设x L G 则S * x由产生式S 则 i T； S2* 2 则 i L G，2所以 x ia 2 L(G) a,b L(G2)同理其中，U S |saS2,不妨设x1a 2L G2ib 2 L(Gi) a,b L(G2)可得 L(G)L(Gi) a,b L(G2)(2)设x L(Gi) a,b L(G2)不妨设 x ia 2 其中L(Gi),2 L(G2)即S1 * 曾 S2由P3中产生式S * i

16、aS21a 2所以 L(G1) a,b L(G2)L G综上可得，L(G) L(Gi) a,b L(G2)_ _ * L(G) L(Gi)解：汨妨假设5成取G=(用U? 4已3) 其中，大全标准文案P=S-a |S1-a C P1USe U Sa S|S1 - a C P1 证明略。(5)L(G) L(G)解：不妨假设5咨(取G=(U? 4己$) 其中.P=Sf a |S1 f a e P1 U Sf a S|S1 - a C P1 证明略。3、设文法G有如下产生式：S 一 aB bAA- a aS bAAB - b bS aBB证明L(G)=co 3中含有相同个数的a和b,且3非空。证：观察

17、发现 A的产生式A- bAA中的bA可以用S来代替，同样 B的产生式B-aBB中的aB 也可以用S代替。这样原来的文法可以化为如下的形式：S 一 aB bA2 a aS SAB- b bS SB进一步地，可以把产生式 A- aS中的S代换，把文法化为如下的形式：S 一 aB bAAf a aaB abA SA*,q Q, (q,xy) ( (q,x),y)B b baB bbA SB7 .设 DFA M=(Q, , ,q0, F),证明：对于 x,y注：采用归纳证明的思路周期律 02282067)证明：(首先对y归纳，对任意x来说，|y| = 0 时，即y=根据 DFA 定义(q, ) q,

18、(q,xy)(q,x)(q, x), )( (q,x), y),故原式成立。当|y| 二 n 时，假设原式成立，故当|y|= n+1时，不妨设 y = wa, |w| = n, |a| = 1根据 DFA定义(q , xa )( (q , x), a ), a ，故(q,xy) (q, xwa) ( (q,xw),a)( ( (q,x), w),a)( (q,x),wa)( (q, x), y)原式成立，同理可证，对任意的 y来说，结论也是成立的。大全标准文案综上所述，原式得证*L(M2)= E*8 .证明：对于任意的 DFA M=(Q, 2 , 8 ,q o, Fi)存在 DFA M2=(Q

19、, 2 , 8 ,q 0F2),使得L ( M) o证明：(1)构造M2。设 DFA M=(Q, 2 , 8 ,q 0, Fi)取 DFA M2=(Q, 2 , S ,q 0, Q- Fi)(2)证明 L(M2)= 2*L (M) *对任息x 2x L(M2)= 2*L (M)8 (q,x)Q- Fi8 ( q,x ) Q并且 8 ( q,x )*并且 x L(Mi)x 2* L (M)10、构造识别下列语言的NFAxx 0,i且好不含形如00勺子用ii(2) x x 0,i且x中含形如i0ii0勺子用.尊 i . 00O0, i二0rQ"0, i(3) x x 0,i且好不含形如i

20、0ii0的子用0, i(4) x x 0,i和x的倒数第i0个字符是i,且以0i结尾大全标准文案0, 10,1(5)xx 0,1且x以0开头以1结尾0, 1(6)xx 0,1且x中至少含有两个10, 10， 10, 1S* (7) x x 0,1且如果x以1结尾，则它的长度为偶数；如果以0结尾，则它的长度为奇数S1(8)xx 0,1且x勺首字符和尾字符相等01大全标准文案(9)x xT x, 0,1 0,10,111.根据给定的NFA构造与之等价的 DFA(1) NFA M1的状态转移函数如表 3-9状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3

21、,q1q2,q1终止状态q3q3,q2q3 q0解答:状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q0,q1q0,q1,q3q0,q2q0,q2q0,q2q0,q1q0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2终止状态q0,q1,q3q0,q1,q2,q3q0, q2,q3q0,q1,q2终止状态q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0, q2终止状态q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1, q2大全标准文案q0q0,q1 0 q0,q1,q301

22、,2q0,q2,q321,2q0,q2q0,q1,q2-2100,10,1q0,q1,q2,q3O图3-9所示NFA等价的DFA13 .试给出一个构造方法，对于任意的NFA Mi (Q1, , 1,q0,Fj ,构造 NFAM2(Q2, , 2,q0,F2)，使得L(M2)L(Mi)注：转化成相应的 DFA进行处理,然后可参考第8题的思路证明:首先构造一个与 NFA M i等价的DFA ,M3根据定理 3.1 (P106), L(M 3)L(Mi)构造 M3(Q3, , 3,q。, F3),其中Q32Q1,F3 Pi,P2Pm |P1, P2PmQ,Pi,P2Pm F1, Pl, P2PmQ,

23、a3(q1.qn, a) P1.Pm1(仙0, a)p.Pm在此基础上 M2, Q2Q3, 23, F2 P1.Pm|P1.PmF3即取所有Mi确定化后不是终结状态的状态为M2的终结状态。为了证明L(M2)L(M3),我们在M 3的基础上M 4 (Q4,4,q0, F4),其中 Q4Q3, 43, F4 Q4 ,即所有 M 1确定化后的状态都为终结状态。显然L(M4)大全x L(M2),(q0,x)F2(q0,x) F3x L(M3),又因为(q0,x) Q3(q0,x) F4(q0,x) L(M4)L(M3)，故 L(M2)L(M3)标准文案.' . . 、 . . * . .同理容

24、易证明L(M2)L(M3)故 L(M2)L(M3),又因为 L(M 3) L(M1),故 L(M2)L(M1)可知，构造的 M2是符合要求的。15. P129 15.(1) 、(2)(1)根据NFAM的状态转移函数，起始状态q0的 闭包为 -CLOSURE q0)= q o, q?。由此对以后每输入一个字符后得到的新状态再做闭包，得到下表：(陶文靖02282085 )状态01 q 0, q 2 q 0, q1q2 q 0, q 1, q2, q3 q 0, q1, q2 q 0, q1, q2, q? q 0, q 1, q2, q3 q 0, q 1, q2, q3 q 0, q 1, q2

25、, q3 q 0, q 1, q2, q3qo= q o, q2, q1= q o, q 1, q2 ,q2=q o, q 1, q2,印,因为q3为终止状态，所以 q2= q 0, q 1,q2,q3为终止状态(2)用上述方法得状态01 q 1, q3 q 332 q 0, q 1, q2, q3 q3 q2 q3 q2 q0, q1 q3 q 0, q 1, q2, q3 q 1 q2 q3 q 0, q 1, q2, q3 q 0, q1 q3 q 1, q2, q3 q 0, q 1, q2, q3 q 1, q2, q3 q 3, q2 q 0, q 1, q2, q3qo= q1,

26、 q3,q1=q 3,q2,q2dq 0, q 1,q2,q3 ,q3= q 0, q 1, q3 ,q4d q 172, q3因为各状态均含有终止状态，所以q。, q 1, q2, q3,q 4均为终止状态注：本题没有必要按照 NFA!ij DFA转化的方法来做，而且从 -NFA到NFA转化时状态没有必要改变，可以完全采用 -NFA中的状态大全标准文案如（1）状态0iqo（开始状态） q 0, q i, q2q3 q 0, q i, q2, q3qi q 0, q i, q2, q3 q i .q2, q3q2 q 0, q i, q2, q3qi q2 q3q3 （终止状态） q 0, q

27、 i, q2, q3 q 0, q i, q2, q3(2)状态0iqo（开始状态）q i q2 q 3 q 0, q i, q2, q3qi q 2 q i q2q2, q2, q3 q 0, q 2, q3q3 （终止状态）空 q 0 16、证明对于 的 FA Mi=(Qi,汇 1, 8i,q0i,Fi), FA Mi=(Q2,汇2, gqog,存在 FA M,使得 L(M)= L(M i) U L(M2)证明：不妨设Q与Q的交集为空(1) 构造 M=(QU QU q 0, E, S , q 0,F )其中：1) E =Ei UE2 F= FiU F22) S (q o, e )= q o

28、i ,q 02对于 q C Q,a C 汇 i 8 (q, a)=8 i(q,a)对于 q Q2, a E 2 , 8 (q, a)=8 2(q,a)(i)证明：i)首先证 L(Mi) U L(M2) £ L(M)设 x e L(Mi) u l(M2),从而有 x e L(Mi)或者 x e l(M2)，当 x e L(Mi)时8 i(q oi ,x) C Fi由M的定义可得：6 ( qo,x ) =8 (qo,ex) =8(8 (qo, e ), x)= 6 (q oi ,q 02,x)= 8 (q oi , x) U 8 (q 02, x)= 8i(qoi , x) U 8 (q

29、oi , x) C Fi U 8 (q oi , x) 即 xC L(M)同理可证当x e L(M2)时xC L(M)大全标准文案故 L(Mi) U L(M2)e L(M)2) 再证明 L(M) C L(Mi) U L(M2)设 x e L(M)贝U 8 ( qo,x ) e F由M的定义：8 ( qo,x ) =8 ( qo, e x) = 3 ( 3 (q 0, e ), x)= 8 (q 01 ,q 02,x) = 8 (qoi , x) U 8 (qo2, x)如果是8 (q 0i , x)因为Q与Q的交集为空而且8 (qo,x) C F F= F 1 U F2则8 (q 0i , x

30、)=8 i(q 01 , x) C Fi 因此 x C L(Mi)如果是8 (q 02 , x)因为Q与Q的交集为空而且8 (qo,x) C F F= F 1 U F2则8 (q 02 , x)=8 2(q 02 , x) C F1 因此 x C L(Mz)因此 xC L(M1) U L(M2) L(M) C L(M1) U L(M2)得证因此 L(M)= L(M 1) U L(M2)17 证明：对于任意的FAM1(Q1, 1, 1,q01,F1), FAM 2(Q2, 2, 2,q02, F2),存在 FA M, 使得 L(M) L(M 1)L(M 2) .证明：令 M(Q1 Q 2, ,

31、,q01,f2)其中8的定义为：1)对 qC Q-f 1 , aEU £ 6 (q , a)= 6 1(q , a);2) 对 q C Q-f 2, aEU £ 8 (q , a)= 8 2(q , a)；3) S(f 1, e )=q 02要证 L(M ) L(M1)L(M 2) ，只需证明L(M1)L(M2)L(M ) ， L(M 1)L(M2) L(M )1. 证明 L(M1)L(M2)L(M )设 x L(M1)L(M2),从而有 x1L(M1)并且 x2 L(M2),使得 x x1x2M 1在处理x1的过程中，经过的状态全部都是 Q1中的状态，所以在定义M时,对

32、q Q1,a , (q,x)(q,a)故 (q01, x1)1(q01,x2) f1M 2在处理x2的过程中，经过的状态全部都是 Q2中的状态，所以在定义M时，对 q Q1,a, (q,x)2(q,a)(q02,x)2(q01,x) f2大全下面证明x L(M )标准文案(q01, x)(q01,x1x2)( (q01,x1 ),x2)( 1 (q01 , x1 ), x2 )( f1, x2 )(f1, x2)( (f1, ),x2)(q02 ,x2 )2 (q02 , x2 ) f2x L(M )2) 再证L(M) L(M1)L(M2)设xL(M),即(q01, x) f2由于M是从qoi

33、启动的，由M的定义可知，M要达到状态f2,必须 先到fi.由于除了对应状态转移 函数式(fi, ) q02的移动 外，不存在从f1出发的任何其他移动，而且该移动是f2的必经 移动,所以,比存在x的前缀x1和后缀x2，使得x x1x2，并且x1 将M从状态q01引导到状态G，乂2将乂从状态q02引导到状态f2 .即(q0i,x)(q0i,xix2)( fi , x2)( fi , x2) (q02 , x2) f2其中 ,(q0i,xi) fi, 说i(q0i,xi) fi;(q02 ,x2) f2, 说2 (q02 ,x2) f2大全标准文案这表明x1L(M1)x2 L(M2) 从而 xx1x2L(M 1)L(M 2 )故 L(M) L(M1)L(M2) 综上所述,L(M) L(M1)L(M2 * (吴丹 02282090 )18.证明：对于任意的 FA M1=Q11 1q01F, FA M2=Q222 q02F2存在 FA M,使得 L M =L M1 I L M2。证明：不妨将这些FA看成DFA取乂= Qi Q2, 1I 2, qoi, qo2 , F对于 a 112, q，P Q, q,p