形式语言与自动机理论试题.doc

1、 形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合,和集合,0,00的幂集 （2x4 ）(1) ,(2) ,0,00,0,00,0,00,0,002. 设=0,1, 请给出上的下列语言的文法 （2x5 ）(1)所有包含子串 01011 的串SX01011YX|0X|1XY|0Y|1Y(2)所有既没有一对连续的 0，也没有一对连续的 1 的串A|A|A”A 0|01|01AA” 1|10|10A”3. 构造识别下列语言的 DFA 2x6 (1) x|x0，1 +且 x 以 0 开头以 1 结尾（设置陷阱状态，当第一个字符为 1 时，进入陷阱状态）1S01100 , 10(2) x|

2、x0，1 +且 x 的第十个字符为 1（设置一个陷阱状态，一旦发现 x 的第十个字符为 0，进入陷阱状态） 1S0 ,10 , 10 , 10 , 10 , 11 0 ,0 , 10 , 10 , 10 , 10 , 1二、判断（正确的写 T，错误的写 F） 5x2 1.设 1R和 2是集合a,b,c,d,e上的二元关系，则 321321)(RR ( T )任取(x.,y), 其中 x,y ，使得 。,edcba321)(),Ryx(),( 321zRzx,edcbaz),),yx),(),( 3231 Ryzzxyzzx 23),RxRy21),(x2.对于任一非空集合 A， A ( T )

3、3.文法 G：S A|AS A a|b|c|d|e|f|g 是 RG ( F )4.3 型语言 2 型语言 1 型语言 0 型语言 ( T )5.s（rs+s） *r=rr s（rr *s） ( F )不成立，假设 r,s 分别是表示语言 R，S 的正则表达式，例如当 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)*,结论不成立三、设文法 G 的产生式集如下，试给出句子 aaabbbccc 的至少两个不同的推导（ 12

4、分） 。aSBC|bbBbbCBBCbCbccCcc推导一： 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四、判断语言 n01|n=1是否为 RL，如果是，请构造出它的有穷描述(

5、FA,RG 或者RL） ；如果不是，请证明你的结论（12 分）解：设 L= n|n=1。假设 L 是 RL，则它满足泵引理。不妨设 N 是泵引理所指的仅依赖于 L 的正整数，取 Z= 显然，ZL 。N01按照泵引理所述，必存在 u，v，w。由于|uv|=1，所以 v 只可能是由 0 组成的非空串。不妨设 v= ， k=1 此时有 u= ，w= 从而有 uv w=k jkN0Nj01i当 i=2 时，有 uv w= 又因为 k=1,NjikjN01)(0 21所以 N+kN 这就是说 不属于 L，Nk这与泵引理矛盾。所以，L 不是 RL。五、构造等价于下图所示 DFA 的正则表达式。(12 分)

6、答案(之一) ：( 01+(1+00)(1+00*1)0)*(1+00*1)1) )* (+(1+00)(1+00*1)0)*00*)预处理：q1q0q2 q3100 01 1 10X YSq1q0q2 q3100 01 1 10去掉 q3：去掉 q1：q1q0q21011+00*10X Y00*q0q21+00(1+00*1)0X Y00*(1+00*1)101去掉 q2：去掉 q0：六、设 M=（ 210,q，0,1，0,1，B， ， 0q,B, 2）,其中 的定义如下：（ 0q，0）=（ ，0 ，R ）（ ，1）=（ 1，1，R）（ ，0）=（ ，0 ，R）（ 1q，B）=（ 2，B，R

7、）请根据此定义，给出 M 处理字符串 00001000,10000 的过程中 ID 的变化。 （10 分）解：处理输入串 00001000 的过程中经历的 ID 变化序列如下：00001000 0 0001000 00 001000 000 01000 0000 100000q0q0q0q00001 0000 000010 00 0000100 0 00001000 00001000B11112处理输入串 10000 的过程中经历的 ID 变化序列如下：10000 1 00000 10 000 100 00 1000 0 10000 10000B0qq1q1q1q1q2七、根据给定的 NFA，

8、构造与之等价的 DFA。 （14 分） NFA M 的状态转移函数如下表 输入字符状态说明 状态0 1 2开始状态 q0 q0,q1 q0,q2 q0,q2q0X Y+(1+00)(1+00*1)0)*00*01+(1+00)(1+00*1)0)*(1+00*1)1)X Y(01+(1+00)(1+00*1)0)*(1+00*1)1)* (+(1+00)(1+00*1)0)*00*)解答：输入字符状态说明 状态0 1 2开始状态 q0 q0,q1 q0,q2 q0,q2q0,q1 q0,q1,q3 q0,q2 q0,q2q0,q2 q0,q1 q0,q1,q2,q3 q0,q1,q2q0,q1

9、,q2 q0,q1,q3 q0,q1,q2,q3 q0,q1,q2终止状态 q0,q1,q3 q0,q1,q2,q3 q0, q2,q3 q0,q2终止状态 q0,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1, q2终止状态 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1, q2q 0 q 0 , q 1 q 0 , q 2 01 , 22 q 0 , q 1 , q 3 q 0 , q 1 , q 2 q 0 , q 2 , q 3 q 0 , q 1 , q 2 , q 3 0 , 122001 , 20210 , 11参 考

10、题 目1、设 ，构造下列语言的文法。,cba(1) 。0|1nLq1 q3,q0 q2q2 q3,q1 q2,q1终止状态 q3 q3,q2 q3 q0解答： 。),|,(1 SabSG(2) 。,|2mnbaL解答： 。),|,|,|,( SbBaABBA(3) 。1|3n解答： ),(3SPbaSGS aAB|aSAB:3PBAABaBabbBbbbAbaaAaa(4) 。1,|4kmnabLkn解答： 。),|,|,(4 SbBaABSbAG(5) 。,|5w解答： 。),|,(5 caWcaWS(6) 。,|6xLT解答： ),(66 SPcbG:PaS|。caW|(7) 。,|7wL

11、T解答： 。,|,7 ScbabScbSG(8) 。 ,|8xT解答： ),(88 PcaXWSP:cbaXbaX|。W|2、给定 RG： ， ，试分别构造满足下列要求的 RG 11(,)GVTPS22,()GVTPSG，并证明你的结论。 12(1)()L1212123321 1*12122121*2 2 VSVSTPPSxLGSxLGLGxTxLSxP 解 ：不 妨 假 设 ， 并 且 ， 令， ， ，其 中 ， 且证 明 ：（ 1） 设 ， 则若 ， 因 为 ， ， 所 以 成 立若 ， 由 产 生 式 ， 不 妨 设 ， 其 中 ，则 ， 因 为 的 产 生 式 包 括 ， 所 以 22

12、1212 *121122132 2121*13 2*2 21 GLGxxSxTSxxPSTSLGxxSLLG， 可 知所 以 （ ） 设 ， 不 妨 设 ， 其 中 ， ， ，时 ， 由 中 且 ， 则所 以 ， 时 ， 由 中时 ， 由 ， 得 所 以212L综 上 ，12()()1212123312 *1211* 2*312*11 VSVGSTPPxLGxLSxGSGLPSSx解 ：不 妨 假 设 ， 并 且 ， 令， ， ，其 中 ， 或证 明 ：（ ） 设 不 妨 设 那 么 可 知由 构 造 方 法 可 知 ， 且 即（ 2） 设 则 ， 由 知 ， 或不 妨 设 则 ，同 理 2

13、212 LLG则所 以 (3)(),(),Gaba其 中 ， b是 两 个 不 同 的 终 极 符 号1212123*321 1* 212*121211 (),() ()VSVSTPPabSxLGSxaxaTLGabbL解 ：不 妨 假 设 ， 并 且 ， 令， ， ，其 中 ， 其 中 且证 明 ：（ ） 设 则 由 产 生 式 ， 不 妨 设则 ， 则 ，所 以 同 理 212 *121212*32112,()(), ()() (),() ,()bxLLSPSaGbGLb可 得（ ） 设不 妨 设 其 中 ， 即 ，由 中 产 生 式所 以综 上 可 得 ， *1(4)()解：P=S|S1

14、P1SSS|S1P1证明略。 1(5)()LG解：P=S|S1P1SS|S1P1证明略。3、设文法 G 有如下产生式： SaBbAAaaSbAABbbSaBB证明 L(G) 中含有相同个数的 a 和 b，且 非空。证：观察发现 A 的产生式 AbAA 中的 bA 可以用 S 来代替，同样 B 的产生式 BaBB 中的 aB 也可以用 S 代替。这样原来的文法可以化为如下的形式：SaBbAAaaSSABbbSSB进一步地，可以把产生式 AaS 中的 S 代换，把文法化为如下的形式：SaBbAAaaaBabASABbbaBbbASB7设 DFA M= ，证明：对于),(0FqQ),(),(,* yxqxyQqyx注：采用归纳证明的思路证明： (周期律 02282067)首先对 y 归纳，对任意 x 来说，|y| = 0 时，即 y=根据 DFA 定义 ,故原式,),(q ),),()( yxqxqy成立。当|y| = n 时，假设原式成立，故当|y|= n+1 时，不妨设 y = wa, |w| = n, |a| = 1根据 DFA 定义 ，故axqxaq),(),( ),(),(),(,),( yxqwaxqwwxq 原式成立，同理可证，对任意的 y 来说，结论也是成立的。