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

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

2、一个陷阱状态,一旦发现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(R R R R R R R ( T 任取(x.,y,其中x,y ,e d c b a ,使得321(,(R R R y x 。 ,(,(321R y z R R z x z ,e d c b a z ,(,(,(321R y z R z x R z x z ,(,(,(,(3231R y z R z x z R y z R z x z 3231,(,(R

3、 R y x R R y x 3231,(R R R R y x 2.对于任一非空集合A ,A2 ( T 3.文法G :S A|AS A a|b|c|d|e|f|g 是RG ( F 4.3型语言2型语言1型语言0型语言 ( F 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 的产生式集如下,试给出句子

4、aaabbbccc 的至少两个不同的推导(12分。 aSBCaBC S | ab aB bB bb CB BC bC bc cC 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=aaab

5、bbccC=aaabbbccc四、判断语言n n n 010|n=1是否为RL ,如果是,请构造出它的有穷描述(FA,RG 或者RL ;如果不是,请证明你的结论(12分解:设L=nnn 010|n=1。假设L 是RL ,则它满足泵引理。不妨设N 是泵引理所指的仅依赖于 L 的正整数,取Z=N N N 010 显然,Z L 。按照泵引理所述,必存在u ,v ,w 。由于|uv|=1,所以v 只可能是由0组成的非空串。不妨设v=k0,k=1 此时有u=jk N -0,w=NN j 010 从而有uv i w=NNj ikjk N 0100(0- 当i=2时,有uv 2w=NNkN 010+ 又因为

6、k=1,所以 N+kN 这就是说NNkN 010+不属于L ,这与泵引理矛盾。所以,L 不是RL 。五、构造等价于下图所示DFA 的正则表达式。(12分答案(之一:( 01+(1+00(1+00*10*(1+00*11 * (+(1+00(1+00*10*00*Sq 1 q 0q 2q 310 111预处理:去掉q3:去掉q1:q1q0q2q310 01 1 1X Yq1q0q2111+00*1X Y00*q0q21+00(1+00*10XY00*(1+00*1101去掉q 2:去掉q 0:六、设M=(210,q q q ,0,1,0,1,B,0q ,B,2q ,其中的定义如下: (0q ,0

7、=(0q ,0,R (0q ,1=(1q ,1,R (1q ,0=(1q ,0,R (1q ,B =(2q ,B ,R 请根据此定义,给出M 处理字符串00001000,10000的过程中ID 的变化。(10分 解:处理输入串00001000的过程中经历的ID 变化序列如下: 0q0000100000q0001000 000q001000 0000q 01000 00000q 10000 000011q00000000101q0000001001q000010001q00001000B 2q 处理输入串10000的过程中经历的ID 变化序列如下: 0q 10000 11q 00000101q0

8、001001q0010001q100001q 10000B 2q七、根据给定的NFA ,构造与之等价的DFA 。(14分 NFA M 的状态转移函数如下表q 0XY+(1+00(1+00*10*00*01+(1+00(1+00*10*(1+00*11XY(01+(1+00(1+00*10*(1+00*11* (+(1+00(1+00*10*00*解答:状态说明状态输入字符1 2 开始状态q0 q0,q1 q0,q2 q0,q2 q0,q1 q0,q1,q3 q0,q2 q0,q2 q0,q2 q0,q1 q0,q1,q2,q3 q0,q1,q2q0,q1,q2 q0,q1,q3 q0,q1,q

9、2,q3 q0,q1,q2 终止状态 q0,q1,q3 q0,q1,q2,q3 q0, q2,q3 q0,q2 终止状态 q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1, q2终止状态q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1, q2q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,1221,20210,11状态说明 状态输入字符1 2 开始状态q0 q0,q1 q0,q2q0,q2q1 q3,q0q2q2q3,q1 q2,q1 终止状态 q3q3,q2q3 q0参 考 题

10、 目1、设,c b a =,构造下列语言的文法。 (1 0|1=n b a L n n 。解答:,|,(1S aSb S b a S G =。 (2 1,|2=m n b a L m n 。解答:,|,|,|,(2S b bB B a aA A B A S b a B A S G =。 (3 1|3=n a b a L n n n 。解答:,(33S P b a B A S G = :3P S aAB|aSAB BA AB aB ab bB bb bA ba aA aa(4 1,|4=k m n a b a L k m n 。解答:,|,|,(4S b bB B a aA A ABA S b

11、a A S G =。(5 ,|5+=w a awa L 。解答:,|,(5S c b a cW bW aW W aWa S c b a W S G =。 (6 ,|6+=w x xwxL T。解答:,(66S P c b a W S G = :6P c W c b W b a W a S | c b a cW bW aW W |。(7 ,|7+=w w w w L T 。解答:,|,7S c b a cWc bWb aWa S c b a W S G =。(8 ,|8+=w x w xx L T 。解答:,(88S P c b a X W S G = XW S P :8c b a c X c

12、b X b a X a X | c b a cW bW aW W |。2、给定RG :11111(,G V T P S =,2222,2(,G V T P S =,试分别构造满足下列要求的RG G ,并证明你的结论。12(1(L G L G L G =(1212121212332111*2222 V V S V V G S VV T T P P P S P S S T S S S S x L G S xx L G L G L G L G x S S x x x x T x L G S x G P x L += 解:不妨假设,并且,令,其中,且证明:(1设,则若,因为,所以成立若,由产生式,不妨

13、设,其中,则,因为的产生式包括,所以(2121212*1321112121212*1312*2221 G x x x L G L G L G L G L G x L G L G x x x x T S x x T S x x P S S T S S x S x x x x L G L G L G L G x P S S S x x S S x x L G L G L G +=,可知所以 (1设,不妨设,其中,时,由中且,则所以,时,由中时,由,得所以(212L G L G L G L G =综上,12(2(L G L G L G =(12121212123312*1211*12*312*111

14、 V V S V V G S VV T T P P P S P S S S x L G L G x L G S xG S x x L G L G L G L G x L G S x P S x S xS x x L G L G L G = 解:不妨假设,并且,令,其中,或证明:(1设不妨设那么可知由构造方法可知,且即(2设则,由知,或不妨设则,同理(21212 L G L G L G L G L G L G L G L G = 则 所以12(3(,(,L G L G a b L G a =其中,b 是两个不同的终极符号(12121212123*322111*212*112211*(,( (V

15、V S V V G S VV T T P P P S P S aS bS T S S S x L G S x S aS x a T S L G L G x a L G a b L G b L G = 解:不妨假设,并且,令,其中,其中且证明:(1设则由产生式,不妨设则,则,所以同理(21212*1211221122*312121212,(,( (,( (,( (,(a b L G L G L G a b L G x L G a b L G x a L G L G S S P S aS a L G a b L G L G L G L G a b L G =可得(2设不妨设其中,即, 由中产生式

16、所以综上可得,*1(4(L G L G =解: P=S |S1P1S S S|S1P1 证明略。1(5(L G L G +=解: P=S |S1P1S S|S1P1 证明略。3、设文法G 有如下产生式: S aB bAA a aS bAAB b bS aBB证明L(G=中含有相同个数的a 和b ,且非空。证:观察发现A 的产生式A bAA 中的bA 可以用S 来代替,同样B 的产生式B aBB 中的aB 也可以用S 代替。这样原来的文法可以化为如下的形式: S aB bAA a aS SAB b bS SB进一步地,可以把产生式A aS 中的S 代换,把文法化为如下的形式: S aB bAA

17、a aaB abA SA B b baB bbA SB7.设DFA M=,(0F q Q ,证明:对于=,(,(,*y x q xy q Q q y x 注:采用归纳证明的思路证明: (周期律 02282067 首先对y 归纳,对任意x 来说,|y| = 0时,即y=根据DFA 定义,(q q =,(,(,(,(y x q x q x q xy q =,故原式成立。当|y| = n 时,假设原式成立,故当|y|= n+1时, 不妨设y = wa, |w| = n, |a| = 1根据DFA 定义=a a x q xa q ,(,(,故,(,(,(,(,(,(y x q wa x q a w x

18、 q a xw q xwa q xy q =原式成立,同理可证,对任意的y 来说,结论也是成立的。综上所述,原式得证*8.证明:对于任意的DFA M 1=(Q,q 0,F 1 存在DFA M 2=(Q,q 0,F 2, 使得L(M 2=*L (M 1。 证明:(1构造M 2。 设DFA M 1=(Q,q 0,F 1 取DFA M 2=(Q,q 0,Q F 1 (2证明L(M 2=*L (M 1对任意x *x L(M 2=*L (M 1(q,xQ F 1(q,x Q 并且(q,x F 1x *并且x L(M 1x *L (M 110、构造识别下列语言的NFA(10,100x x x +且中不含形

19、如的子串1101011S(20,110110x x x +且中含形如的子串10110,10,1(30,1x x x +且中不含形如10110的子串10110,10,1(40,110101x x x +和的倒数第个字符是,且以结尾0,110,10,10,10,10,100,110,1(50,101x x x +且以开头以结尾010,1(60,1x x x +且中至少含有两个1S0,1110,10,10,1*(70,1x x x 且如果以1结尾,则它的长度为偶数;如果以0结尾,则它的长度为奇数S10,1(80,1x x x +且的首字符和尾字符相等00,10,100111(9,0,1Tx xx +

20、0,100110,111.根据给定的NFA ,构造与之等价的DFA . (1 NFA M 1 的状态转移函数如表3-9 状态说明状态输入字符1 2 开始状态q0 q0,q1 q0,q2q0,q2q1 q3,q0q2q2 q3,q1q2,q1 终止状态 q3 q3,q2 q3 q0解答:状态说明状态输入字符1 2 开始状态q0 q0,q1 q0,q2 q0,q2 q0,q1 q0,q1,q3 q0,q2 q0,q2 q0,q2 q0,q1 q0,q1,q2,q3 q0,q1,q2q0,q1,q2 q0,q1,q3 q0,q1,q2,q3 q0,q1,q2 终止状态 q0,q1,q3 q0,q1,

21、q2,q3 q0, q2,q3 q0,q1,q2 终止状态 q0,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0, q2终止状态q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1, q2q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,1221,20210,11图3-9所示NFA 等价的DFA13.试给出一个构造方法,对于任意的NFA ,(10111F q Q M =,构造NFA =2M,(2022F q Q ,使得(1*2M L M L -=注:转化成相应的DFA 进行处理,然后可参考第8题

22、的思路证明:首先构造一个与NFA 1M 等价的DFA ,3M 根据定理3.1(P106,(13M L M L = 构造,(30333F q Q M =其中=a Q p p p F p p p Q p p p p p p F Q m m m m Q ,.,.,.,|.,2 .,.(.,.(111113m n m n p p a q q p p a q q =在此基础上2M ,3232=Q Q .|.3112=F p p p p F m m 即取所有1M 确定化后不是终结状态的状态为2M 的终结状态。 为了证明(3*2M L M L -=,我们在3M 的基础上=4M,(4044F q Q ,其中,

23、3434=Q Q 44Q F =,即所有1M 确定化后的状态都为终结状态。显然,(*4=M L,(2M L x 则20,(F x q ,(,(330M L x F x q 又因为,(,(,(04030x q F x q Q x q ,(*4=M L 故x (3*M L -,故(3*2M L M L -同理容易证明(3*2M L M L -故(3*2M L M L -=,又因为(13M L M L =,故(1*2M L M L -=可知,构造的2M 是符合要求的。15.P129 15.(1、(2(1根据NFAM 3的状态转移函数,起始状态q 0的闭包为 -CLOSURE (q 0= q 0, q

24、 2。由此对以后每输入一个字符后得到的新状态再做闭包,得到下表: (陶文婧 02282085 状态 01 q 0, q 2 q 0, q 1,q 2 q 0, q 1,q 2,q 3 q 0, q 1,q 2 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 2,q 3q 0= q 0, q 2,q 1= q 0, q 1,q 2,q 2= q 0, q 1,q 2,q 3,因为q 3为终止状态,所以q 2= q 0, q 1,q 2,q 3为终止状态Sq 1q 2q 000,10,1(

25、2用上述方法得 状态 01 q 1, q 3 q 3,q 2 q 0, q 1,q 2,q 3 q 3,q 2 q 3,q 2 q 0, q 1,q 3 q 0, q 1,q 2,q 3 q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 0, q 1,q 3 q 1,q 2,q 3 q 0, q 1,q 2,q 3 q 1,q 2,q 3 q 3,q 2 q 0, q 1,q 2,q 3q 0= q 1, q 3,q 1= q 3,q 2,q 2= q 0, q 1,q 2,q 3,q 3= q 0, q 1,q 3,q 4= q 1,q 2,q 3因为各状态均含有终止状态,所以q

26、 0, q 1,q 2,q 3,q 4均为终止状态1Sq 1q 2q 0q 4q 310011注:本题没有必要按照NFA 到DFA 转化的方法来做,而且从-NFA 到NFA 转化时状态没有必要改变,可以完全采用-NFA 中的状态如(1状态0 1q0(开始状态 q0, q1,q2 q3 q0, q1,q2,q3q1 q0, q1,q2,q3 q1,q2,q3q2 q0, q1,q2,q3 q1,q2,q3q3(终止状态 q0, q1,q2,q3 q0, q1,q2,q3(2状态0 1q0(开始状态 q1 q2q3, q0, q1,q2,q3q1 q2 q1,q2q2,q2,q3 q0, q2,q

27、3q3(终止状态空 q0 16、证明对于的FA M1=(Q1,1,1,q01,F1,FA M1=(Q2,2,2,q02,F2,存在FA M,使得L(M= L(M1L(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(M1L(M2L(M设x L(M1L(M2,从而有x L(M1或者x L(M2,当x L(M1时1(q01,xF1由M的定义可得:(q0,x=(q0,x=(q0, x=(q01 ,q02,

28、x=(q01 , x(q02, x=1(q01 , x (q01 , xF1(q01 , x 即xL(M同理可证当x L(M2时xL(M故L(M1L(M2L(M2 再证明L(ML(M 1L(M 2设x L(M 则(q 0,x F 由M 的定义:(q 0,x =(q 0,x =(q 0, x=(q 01 ,q 02,x =(q 01 , x(q 02, x 如果是(q 01 , x 因为Q 1 与Q 2的交集为空 而且(q 0,x F F= F 1F 2 则 (q 01 , x= 1(q 01 , xF 1 因此x L(M 1如果是(q 02 , x 因为Q 1 与Q 2的交集为空 而且(q 0

29、,x F F= F 1F 2 则 (q 02 , x= 2(q 02 , xF 1 因此x L(M 2因此x L(M 1L(M 2 L(ML(M 1L(M 2得证 因此L(M= L(M 1L(M 217 证明:对于任意的FA ,(,(20222221011111F q Q FAMF q Q M =L(M L(M L(MM,FA 21=使得存在.证明:令 ,其中的定义为: 1 对q Q 1-f 1,a (q ,a=1(q ,a;2 对q Q 2-f 2,a (q ,a=2(q ,a; 3 (f 1,=q 02 要证 , 只需证明 ,1. 证明,(20121f q Q Q M = (21M L M

30、 L ML =(21M L M L M L (21M L M L M L 21221121,(,(x x x M L x M L x M L M L x =使得并且从而有设中的状态经过的状态全部都是的过程中在处理(,(,(,(,(,20122021222M L x f x q x q a q x q a Q q M Q x M =下面证明对时所以在定义中的状态经过的状态全部都是的过程中在处理(21M L M L M L 2 再证明(,(,(,(,(,(,(,(,(,(22022202212121210112101210101MLxfxqxqxfxfxfxxqxxqxxqxq=即得证,(,(;,

31、(,(,(,(,(,(,(.,x,xxx,xxx,(.,(,(2202222021101111012202212121010120221011212121021120120121fxqfxqfxqfxqfxqxfxfxxqxqfqMxfqMffqfffMMqMfxqMLxMLMLML=说明说明其中即引导到状态从状态将引导到状态从状态将并且使得和后缀的前缀比存在所以移动的必经而且该移动是出发的任何其他移动不存在从外的移动函数式由于除了对应状态转移先到必须要达到状态的定义可知由启动的是从由于即设2(ML M L M L M L M L M L M L M L x x x M L x M L x =综上所述故从而这表明* (吴丹 02282090(218.FA M Q q F FA M Q q F FA M L M L M L M FA D FAM Q Q q q F a Q ,q,p a q a p a .x L M 1 2.1,x x x xk xi i k