《形式语言与自动机理论精彩试题》由会员分享，可在线阅读，更多相关《形式语言与自动机理论精彩试题（21页珍藏版）》请在金锄头文库上搜索。
1、标准文案形式语言与自动机理论试题、按要求完成下列填空1） 给出集合,和集合 ,0,00的哥集 （2x4 ），2） ） ， e ,0,00, ,0, s ,00,0,00, s ,0,002. 设汇=0,1,请给出汇上的下列语言的文法（2x5）(1)所有包含子串 01011的串S一 X01011YX一 |0X|1XY一 e|0Y|1Y2) )所有既没有一对连续的0,也没有一对连续的1的串A一 e |A |AA一 0101101A A” 一 1110110A ”、.一 3) 构造识别下列语百的DFA 2x6(1) x|x 0, 1+且x以0开头以1结尾(设置陷阱状态，当第一个字符为1时，进入陷阱状
2、态)(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型语言 2型语言RiRiRiRiR3RiR3R2(z, y)R3)za,b,c,d,e(x, z)(z, y)(x, y)R2R32
3、aa|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)三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导(i2分)。S aBC|aSBCaB abbB 一 b
4、bCB f BCbC 一 bccC 一 cc推导一：S=aSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC标准文案=aaabbCBCC =aaabbBCCC =aaabbbCCC =aaabbbcCC =aaabbbccC =aaabbbccc推导二：S=aSBC=aaSBCBC=aaaBCBCBC=aaaBBCCBC=aaaBBCBCC=aaabBCBCC =aaabbCBCC=aaabbBCCC =aaabbbCCC =aaabbbcCC=aaabbbccC=aaabbbccc四、判断语言 0n1n0n|n=1是否为RL,如果是，请构造
5、出它的有穷描述（FA,RG或者RL）;如果不是，请证明你的结论（12分）解：设L= 0n1n0n|n=1。假设L是RL,则它满足泵引理。不妨设 N是泵引理所指的仅依赖于L的正整数，取Z=0N1N0N 显然，ZCL。按照泵引理所述，必存在 u, v, w。由于|uv|=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+kN这就是说0N k1N0N不属于L,这与泵引理矛盾。所以，L不是RL。五、构造等价于下图所示DFA的
6、正则表达式。（12分）标准文案)*答 案 (之 一)：(01+(1+00)(1+00*1)0)*(1+00*1)1)(+(1+00)(1+00*1)0)*00*)去掉q3：q2去掉qi：大全去掉q2：01+(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*)0,1 , 0,1 , B, 8, C0,B, Q),其中 8 的定义如下:s（ q, 0）= （qb，0, R）8（ “，1）= （q，1, R）s（ q, 0）=（ q, 0, R）s（ q, B）= g, b,
7、 R）请根据此定义，给出 M处理字符串00001000,10000的过程中ID的变化。（10分） 解：处理输入串 00001000的过程中经历的ID变化序列如下：000010000 q0000100000 q00010001 000 q0010000000 q010000卜M 00001 q1 0000000010 q1 000000100 q10h:l00001000q11 M100001000Bq2处理输入串10000的过程中经历的ID变化序列如下:q0100001 q1 0000010 q1000hi100 q1 00 1000 q1010000 q1.10000Bq2q0q0,q1,q
8、31q0,q2,q3q0,q2q0,q1,q2一一一200，10,1 q0,q1,q2,q32七、根据给定的 NFA构造与之等价的 DFA （14分） NFA M的状态转移函数如下表状态说明状态输入字符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
9、,q1,q2,q3q0, q2,q3q0,q2终止状态q0,q2,q3q0,q1,q2,q3q0,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
10、faAB|aSABBA fAB aB f ab bB f bb bA fba aA 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 。
11、解答： G7 S,W, a,b,c, S aWa |bWb |cWc |a | b |c, 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 MFRS),试分别构造满足下列要求的RG G并证明你的结论。(1)L(G) L(Gi)L(G2)解：不妨假设MI v2,并且S V1UV2,令G S UV1UV2,1 UT2, P U P2 UP3, S其中，P5ss21且 sU SSiU S证明：、一
12、一， *(1)设x L G ,则S x若x，因为 L G , L G2 ,所以 L G1 L G2成立若x,由产生式SS2,不妨设xxx2,其中xiTi,xiLGi则S2* x2,因为G的产生式包括P2,所以x2LG2,可知xxix2L G LG2所以 LG L G L G2*-r-*(i)设xLGiLG2,不妨设 xxix2,其中 x1T，x1，x2T2 ,S2x2xi时，由 B 中 SS2Ti 且 ，则 Sx1s2xix2所以 xix2 L G , L Gi L G2L Gxi时，由中 SI SiS * x2x2时，由S,得Sx2所以x2 L GL Gi L G2L G综上，LG L G1
13、 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, b是两个不同的终极符号解：不妨假设 V11V2,并且S V1 UV2,令G S UV1 UV2, T1UT2,
