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

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 ”a0|01|01a a”1|10|10a ”3.构造识别下列语言的dfa 2x6(1) x|x0，1+且 x 以 0 开头以 1 结尾 （设置陷阱状态，当第一个字符为1 时，进入陷阱状态）1s01100,10(2) x|x0，1+且 x

2、 的第十个字符为1（设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态）1s0,10,10,10,10,110,0,10,10,10,10,1二、判断（正确的写t，错误的写f）5x21. 设1r和2r是 集 合 a,b,c,d,e 上 的 二 元 关 系 ， 则3231321)(rrrrrrr( t )任取 (x.,y),其中 x,y,edcba，使得321)(),(rrryx。),(),(321ryzrrzxz,edcbaz),(),(),(321ryzrzxrzxz),(),(),(),(3231ryzrzxzryzrzxz3231),(),(rryxrryx3231),(rrr

3、ryx2.对于任一非空集合a，a2( t )3.文法 g：s a|as a a|b|c|d|e|f|g 是 rg ( f )型语言2 型语言1 型语言0 型语言( t )（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)*rrr*s(rr*s)*, 结论不成立三、设文法g 的产生式集如下，试给出句子aaabbbccc 的至少两个不同

4、的推导（12 分） 。asbcabcs|ababbbbbcbbcbcbccccc推导一：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四、判断语言 nnn010|n=1 是否为rl

5、 ，如果是，请构造出它的有穷描述(fa,rg或者 rl ） ；如果不是，请证明你的结论（12 分）解：设 l=nnn010|n=1 。假设 l 是 rl ，则它满足泵引理。不妨设n 是泵引理所指的仅依赖于 l的正整数，取z=nnn010显然， z l 。按照泵引理所述，必存在u，v，w。由于 |uv|=1 ，所以v 只可能是由0 组成的 非 空 串 。 不 妨 设v=k0， k=1 此 时 有u=jkn0， w=nnj010从 而 有uviw=nnjikjkn010)0(0当 i=2 时，有 uv2w=nnkn010又因为 k=1,所以n+kn 这就是说nnkn010不属于 l，这与泵引理矛盾

6、。所以，l 不是 rl。五、构造等价于下图所示dfa的正则表达式。(12 分) 答案 (之一 )：( 01+(1+00)(1+00*1)0)*(1+00*1)1) )* (+(1+00)(1+00*1)0)*00*)sq1q0q2q310001110预处理：去掉 q3：去掉 q1：q1q0q2q310001110xyq1q0q21011+00*10xy00*q0q21+00(1+00*1)0xy00*(1+00*1)101去掉 q2：去掉 q0：六、设 m=（210,qqq，0,1， 0,1， b， ，0q,b,2q）,其中 的定义如下： （0q，0）=（0q，0，r） （0q，1）=（1q，

7、1，r） （1q，0）=（1q，0，r） （1q，b）=（2q，b，r）请根据此定义，给出m 处理字符串00001000,10000 的过程中id 的变化。（10 分）解：处理输入串00001000 的过程中经历的id 变化序列如下：0q00001000 00q0001000 000q001000 0000q01000 00000q10000000011q0000 0000101q00 00001001q0 000010001q00001000b2q处理输入串10000 的过程中经历的id 变化序列如下：0q10000 11q00000 101q000 1001q00 10001q0 1000

8、01q10000b2qq0xy+(1+00)(1+00*1)0)*00*01+(1+00)(1+00*1)0)*(1+00*1)1)xy(01+(1+00)(1+00*1)0)*(1+00*1)1)* (+(1+00)(1+00*1)0)*00*)七、根据给定的nfa ，构造与之等价的dfa 。 （14 分）nfa m 的状态转移函数如下表解答：状态说明状态输入字符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终止状态q

9、0,q1,q3q0,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, q2q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,122001,20210,11状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,q1q2,q1终止状态q3q3,q2q3 q0参 考 题 目1、设,cba，构造下列语言的文法。(1) 0|1nbalnn。

10、解答：),|,(1sasbsbasg。(2) 1,|2mnbalmn。解答：),|,|,|,(2sbbbbaaaabasbabasg。(3) 1|3nabalnnn。解答：),(33spbabasg:3ps aab|asabbaabababbbbbbabaaaaa(4) 1,|4kmnabalkmn。解答：),|,|,(4sbbbbaaaaabasbaasg。(5) ,|5waawal。解答：),|,(5scbacwbwawwawascbawsg。(6) ,|6wxxwxlt。解答：),(66spcbawsg: 6pcwcbwbawas|cbacwbwaww|。(7) ,|7wwwwlt。解答

11、：,|,7scbacwcbwbawascbawsg。(8) ,|8wxwxxlt。解答：),(88spcbaxwsgxwsp :8cbacxcbxbaxax|cbacwbwaww|。2、给定 rg：11111(,)gv t p s，2222,2(,)gvtp s，试分别构造满足下列要求的rg g ，并证明你的结论。12(1) ()() ()l gl gl g1212121212332111*12122121111*2222vvsvvgsvvttpppspsstssssxl gsxxl gl gl gl gxssxx xxtxl gsxgpxliuuuuuuuu解：不妨假设，并且，令，其中，且证

12、明：（1）设，则若，因为，所以成立若，由产生式，不妨设，其中，则，因为的产生式包括，所以2121212*1212111122221321112121212*1312*2221gxx xl gl gl gl gl gxl gl gxx xxtsxxtsxxpsstssx sx xx xl gl gl gl gxpsssxxssxxl gl gl g，可知所以（1）设，不妨设，其中，时，由中且，则所以，时，由中时，由，得所以212l gl gl gl g综上，12(2)()()()l gl gl gu12121212123312*1211*12*312*111vvsvvgsvvttpppspsss

13、xl gl gxl gsxgsxxl gl gl gl gxl gsxpsxsxsxxl gl gl giuuuuuuuu解：不妨假设，并且，令，其中，或证明：（1）设不妨设那么可知由构造方法可知，且即（2）设则，由知，或不妨设则，同理21212l gl gl gl gl gl gl gl guu则所以12(3) ()(),(),l gl ga b l ga其中 ，b是两个不同的终极符号12121212123*322111*212*112211221212121(),() ()vvsvvgsvvttpppspsasbstsssxl gsxsasxatsl gl gxal ga b l gbl

14、giuuuuuuu解：不妨假设，并且，令，其中，其中且证明：（1）设则由产生式，不妨设则，则，所以同理21212*1211221122*312121212,()()(),() (),() ()() (),() ()(),()a b l gl gl ga b l gxl ga b l gxal gl gsspsasal ga b l gl gl gl ga b l g可得（2）设不妨设其中，即，由中产生式所以综上可得，*1(4)()()l gl g解：p=s |s1 p1s s s|s1 p1证明略。1(5)()()l gl g解：p=s |s1 p1s s|s1 p1证明略。3、设文法g 有如

15、下产生式：sabbaaaasbaabbbsabb证明 l(g)中含有相同个数的a 和 b，且非空 。证：观察发现a的产生式abaa 中的 ba 可以用 s来代替，同样b 的产生式 babb中的ab也可以用s代替。这样原来的文法可以化为如下的形式：sabbaaaassabbbssb进一步地，可以把产生式aas中的 s代换，把文法化为如下的形式：sabbaaaaab aba sabbbab bba sb7设 dfa m=),(0fqq，证明：对于),(),(,*yxqxyqqqyx注：采用归纳证明的思路证明：(周期律 02282067)首先对 y 归纳，对任意x 来说， |y| = 0 时，即 y

16、=根据 dfa定义,),(qq),(),(),(),(yxqxqxqxyq,故原式成立。当|y| = n 时，假设原式成立，故当|y|= n+1 时，不妨设 y = wa, |w| = n, |a| = 1根据 dfa定义aaxqxaq),),(),(，故),(),(),),(),(),(),(yxqwaxqawxqaxwqxwaqxyq原式成立，同理可证，对任意的y 来说，结论也是成立的。综上所述，原式得证*8证明 :对于任意的dfa m1=(q,q0,f1) 存在 dfa m2=(q, ,q0,f2), 使得 l(m2)=*l（m1） 。证明： （1）构造 m2。设 dfa m1=(q,q

17、0,f1) 取 dfa m2=(q,q0,q f1)（2）证明 l(m2)=*l（m1）对任意 x*xl(m2)=*l（m1）(q,x)qf1（ q,x）q 并且（ q,x）f1x*并且 xl(m1)x*l（m1）10、构造识别下列语言的nfa (1)0,100 x xx且 中不含形如的子串1101011s(2)0,110110 x xx且 中含形如的子串101100，10，1(3)0,1x xx且 中不含形如 10110的子串101100，10，1(4)0,110101x xx和 的倒数第个字符是 ，且以结尾0，110，10，10，10，10，100，110，1(5)0,101x xx且 以

18、 开头以 结尾010，1(6)0,1x xx且 中至少含有两个 1s0，1110，10，10，1*(7)0,1x xx且如果 以1结尾，则它的长度为偶数；如果以 0结尾，则它的长度为奇数s10，10(8)0,1x xx且 的首字符和尾字符相等00，10，100111(9),0,1 tx xx0,100110,111.根据给定的nfa，构造与之等价的dfa. （1） nfa m1 的状态转移函数如表3-9状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,q1q2,q1终止状态q3q3,q2q3 q0解答：状态说明状态输入字符012开始状态q0q0,q

19、1q0,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, q2q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,122001,20210,11图 3-9 所

20、示 nfa等价的 dfa13 试 给 出 一 个 构 造 方 法 ， 对 于 任 意 的nfa ),(10111fqqm， 构 造nfa 2m),(2022fqq，使得)()(1*2mlml注：转化成相应的dfa进行处理，然后可参考第8 题的思路证明：首先构造一个与nfa 1m等价的 dfa ，3m根据定理（ p106） ，)()(13mlml构造), ,(30333fqqm其中aqpppfpppqppppppfqmmmmq,.,., ,., |.,2211212121331.),.(.),.(111113mnmnppaqqppaqq在此基础上2m，,3232qq. | .3112fppppf

21、mm即取所有1m确定化后不是终结状态的状态为2m的终结状态。为了证明)()(3*2mlml， 我们在3m的基础上4m),(4044fqq，其中,3434qq44qf，即所有1m确定化后的状态都为终结状态。显然,)(*4ml),(2mlx则20),(fxq),(),(330mlxfxq又 因 为),(),(),(04030 xqfxqqxq,)(*4ml故x)(3*ml，故)()(3*2mlml同理容易证明)()(3*2mlml故)()(3*2mlml，又因为)()(13mlml，故)()(1*2mlml可知，构造的2m是符合要求的。15p129 15.(1)、 （2）（1）根据 nfam3的状

22、态转移函数，起始状态q0的闭包为-closure （q0）= q0, q2。由此对以后每输入一个字符后得到的新状态再做闭包，得到下表：（陶文婧02282085）状态01 q0, q2 q0, q1，q2 q0, q1，q2，q3 q0, q1，q2 q0, q1，q2，q3 q0, q1，q2，q3 q0, q1，q2，q3 q0, q1，q2，q3 q0, q1，q2，q3q0= q0, q2，q1= q0, q1，q2，q2= q0, q1，q2，q3，因为 q3为终止状态，所以q2= q0, q1，q2，q3为终止状态sq1q2q000，10，1（2）用上述方法得状态01 q1, q3

23、q3，q2 q0, q1，q2，q3 q3，q2 q3，q2 q0, q1，q3 q0, q1，q2，q3 q1，q2，q3 q0, q1，q2，q3 q0, q1，q3 q1，q2，q3 q0, q1，q2，q3 q1，q2，q3 q3，q2 q0, q1，q2，q3q0= q1, q3，q1= q3，q2，q2= q0, q1，q2，q3，q3= q0, q1，q3，q4= q1，q2，q3因为各状态均含有终止状态，所以q0, q1，q2，q3,q4均为终止状态1s0q1q2q0q40q310011注：本题没有必要按照nfa到 dfa转化的方法来做，而且从-nfa到 nfa 转化时状态没有

24、必要改变，可以完全采用-nfa中的状态如（ 1）状态01q0(开始状态 ) q0, q1，q2 q3 q0, q1，q2，q3q1 q0, q1，q2，q3 q1，q2，q3q2 q0, q1，q2，q3q1，q2，q3q3（终止状态） q0, q1，q2，q3 q0, q1，q2，q3(2) 状态01q0(开始状态 ) q1 q2q3， q0, q1，q2，q3q1 q2 q1，q2q2，q2，q3 q0, q2，q3q3（终止状态）空 q0 16、证明对于的 fa m1=(q1,1,1,q01,f1)， fa m1=(q2,2,2,q02,f2)，存在 fa m，使得l(m)= l(m1)

25、l(m2) 证明：不妨设q1 与 q2的交集为空（1）构造 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(m1)l(m2)l(m)设 x l(m1)l(m2)，从而有x l(m1)或者 x l(m2)，当 x l(m1)时1(q01,x)f1由 m 的定义可得：（ q0,x）=（ q0,x）=(q0,), x)=(q01 ,q02,x)=(q01 , x) (q02, x)=1(q01 , x) (q01 , x)f

26、1 (q01 , x) 即 xl(m)同理可证当x l(m2)时 xl(m)故 l(m1)l(m2)l(m)2) 再证明 l(m)l(m1)l(m2)设 xl(m) 则（ q0,x） f由 m 的定义：（ q0,x）=（ q0,x）=(q0,), x)=(q01 ,q02,x) =(q01 , x) (q02, x)如果是 (q01 , x) 因为 q1 与 q2的交集为空而且（ q0,x） f f= f1f2则(q01 , x)= 1(q01 , x)f1 因此 x l(m1)如果是 (q02 , x) 因为 q1 与 q2的交集为空而且（ q0,x） f f= f1f2则(q02 , x)

27、= 2(q02 , x) f1 因此 x l(m2)因此 xl(m1)l(m2) l(m)l(m1) l(m2)得证因此 l(m)= l(m1)l(m2)17 证明：对于任意的fa),(),(20222221011111fqqfamfqqm)l(ml(ml(m)m,fa 21使得存在.证明：令,其中的定义为：1) 对qq1-f1，a (q，a)=1(q，a)；2) 对qq2-f2，a (q，a)=2(q，a)；3) (f1， )=q02要证，只需证明，1.证明) ,(20121fqqqm)()()(21mlmlml)()()(21mlmlml)()()(21mlmlml21221121),()

28、(),()(xxxmlxmlxmlmlx使得并且从而有设),(),(),(),(,1201110111111fxqxqaqxqaqqmqxm故对时所以在定义中的状态经过的状态全部都是的过程中在处理)(),(),(),(),(,20122021222mlxfxqxqaqxqaqqmqxm下面证明对时所以在定义中的状态经过的状态全部都是的过程中在处理)()()(21mlmlml2) 再证明)(),(),(),(),(),(),(),(),(),(22022202212121210112101210101mlxfxqxqxfxfxfxxqxxqxxqxq即得证),(,),(;),(,),(,),()

29、,(),(),(),(.,x,xxx,xxx,),(.,),(),()()()(2202222021101111012202212121010120221011212121021120120121fxqfxqfxqfxqfxqxfxfxxqxqfqmxfqmffqfffmmqmfxqmlxmlmlml说明说明其中即引导到状态从状态将引导到状态从状态将并且使得和后缀的前缀比存在所以移动的必经而且该移动是出发的任何其他移动不存在从外的移动函数式由于除了对应状态转移先到必须要达到状态的定义可知由启动的是从由于即设212121212211()()(,)()()()()()()(mlmlmlmlmlmlmlmlxxxmlxmlx综上所述故从而这表明*（吴丹02282090）11110112202212121201121218.fa mqqffa mqqffa ml ml ml mfadfamqqqqfaq,q,paqapa.xl m1 2.1,xx xxkxi ikiii，2，2，02证明：对于任意的，存在，使得。证明：不妨将这些看成取， ，对于，q,p，1