形式语言与自动机理论试题.doc_文客久久网wenke99.com

资源描述

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参考

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 来说，结论也是成立的。

展开阅读全文