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

《形式语言与自动机理论试题.pdf》由会员分享，可在线阅读，更多相关《形式语言与自动机理论试题.pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 形式语言与自动机理论试题 一、按要求完成下列填空 1.给出集合,和集合,0,00的幂集 （2x4）(1),(2),0,00,0,00,0,00,0,00 2.设=0,1,请给出上的下列语言的文法 （2x5）(1)所有包含子串 01011 的串 SX01011Y 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|x0，1+且 x 以 0 开头以 1 结尾 （设置陷阱状态，当第一个字符为 1 时，进入陷阱状态）1S01100,10 (2)x|x0，1

2、+且 x 的第十个字符为 1 （设置一个陷阱状态，一旦发现 x 的第十个字符为 0，进入陷阱状态）1S0,10,10,10,10,110,0,10,10,10,10,1 二、判断（正确的写 T，错误的写 F）5x2 1.设1R和2R是 集 合 a,b,c,d,e 上 的 二 元 关 系，则3231321)(RRRRRRR (T)任取(x.,y),其中 x,y,edcba，使得321)(),(RRRyx。),(),(321RyzRRzxz ,edcbaz ),(),(),(321RyzRzxRzxz ),(),(),(),(3231RyzRzxzRyzRzxz 3231),(),(RRyxRRy

3、x 3231),(RRRRyx 2.对于任一非空集合 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)*r rr*s(rr*s)*,结论不成立 三、设文法 G 的产生式集如下，试给出句子 aaabbbccc

4、 的至少两个不同的推导（12 分）。aSBCaBCS|abaB bBbb CBBC bCbc cCcc 推导一：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 四、判断语

5、言nnn010|n=1是否为 RL，如果是，请构造出它的有穷描述(FA,RG 或者 RL）；如果不是，请证明你的结论（12 分）解：设 L=nnn010|n=1。假设 L 是 RL，则它满足泵引理。不妨设 N 是泵引理所指的仅依赖于 L 的正整数，取 Z=NNN010 显然，ZL。按照泵引理所述，必存在 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不属于

6、L，这与泵引理矛盾。所以，L 不是 RL。五、构造等价于下图所示 DFA 的正则表达式。(12 分)答案(之一)：(01+(1+00)(1+00*1)0)*(1+00*1)1)*(+(1+00)(1+00*1)0)*00*)S q1 q0 q2 q3 1 0 0 0 1 1 1 0 预处理：去掉 q3：去掉 q1：q1 q0 q2 q3 1 0 0 0 1 1 1 0 X Y q1 q0 q2 1 0 1 1+00*1 0 X Y 00*q0 q2 1+00(1+00*1)0 X Y 00*(1+00*1)1 01 去掉 q2：去掉 q0：六、设 M=（210,qqq，0,1，0,1，B，0q

7、,B,2q）,其中 的定义如下：（0q，0）=（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 变化序列如下：0q00001000 00q0001000 000q001000 0000q01000 00000q10000 000011q0000 0000101q00 00001001q0 000010001q 00001000B2q 处理输入串 10000 的过程中经历的 ID 变化

8、序列如下：0q10000 11q00000 101q000 1001q00 10001q0 100001q 10000B2q q0 X 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*)七、根据给定的 NFA，构造与之等价的 DFA。（14 分）NFA M 的状态转移函数如下表 解答：状态说明 状态 输入字符 0 1 2 开始状态 q0 q0,q1 q0,q2 q0,q2 q0,q1 q0,q1,q3 q0,q2 q0,q2

9、q0,q2 q0,q1 q0,q1,q2,q3 q0,q1,q2 q0,q1,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,q2 q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,122001,20210,11 状态说明 状态 输入字符 0 1 2 开

10、始状态 q0 q0,q1 q0,q2 q0,q2 q1 q3,q0 q2 q2 q3,q1 q2,q1 终止状态 q3 q3,q2 q3 q0 参 考 题 目 1、设,cba，构造下列语言的文法。(1)0|1nbaLnn。解答：),|,(1SaSbSbaSG。(2)1,|2mnbaLmn。解答：),|,|,|,(2SbbBBaaAABASbaBASG。(3)1|3nabaLnnn。解答：),(33SPbaBASG :3P S aAB|aSAB BAAB aBab bBbb bAba aAaa (4)1,|4kmnabaLkmn。解答：),|,|,(4SbbBBaaAAABASbaASG。(5)

11、,|5waawaL。解答：),|,(5ScbacWbWaWWaWaScbaWSG。(6),|6wxxwxLT。解答：),(66SPcbaWSG :6PcWcbWbaWaS|cbacWbWaWW|。(7),|7wwwwLT。解答：,|,7ScbacWcbWbaWaScbaWSG。(8),|8wxwxxLT。解答：),(88SPcbaXWSG XWSP:8 cbacXcbXbaXaX|cbacWbWaWW|。2、给定 RG：11111(,)GV T P S，2222,2(,)GV T P S，试分别构造满足下列要求的 RG G，并证明你的结论。12(1)()()()L GL G L G 12121

12、21212332111*12122121111*2222 VVSVVGSVVTTPPPSPSSTSSSSxL GSxxL GL GL GL GxSSxx xxTxL GSxGPxL 解：不妨假设，并且，令，其中，且证明：（1）设，则若，因为，所以成立若，由产生式，不妨设，其中，则，因为的产生式包括，所以 2121212*1212111122221321112121212*1312*2221 Gxx xL GL GL GL GL GxL GL Gxx xxTSxxTSxxPSSTSSx Sx xx xL GL GL GL GxPSSSxxSSxxL GL GL G，可知所以（1）设，不妨设，其中

13、，时，由中且，则所以，时，由中时，由，得所以 212L GL GL GL G综上，12(2)()()()L GL GL G 12121212123312*1211*12*312*111 VVSVVGSVVTTPPPSPSSSxL GL GxL GSxGSxxL GL GL GL GxL GSxPSxSxSxxL GL GL G解：不妨假设，并且，令，其中，或证明：（1）设不妨设那么可知由 构造方法可知，且即（2）设则，由 知，或不妨设则，同理 21212 L GL GL GL GL GL GL GL G则 所以 12(3)()(),(),L GL Ga b L Ga其中，b 是两个不同的终极符

14、号 12121212123*322111*212*112211221212121 (),()()VVSVVGSVVTTPPPSPSaSbSTSSSxL GSxSaSxaTSL GL GxaL Ga b L GbL G 解：不妨假设，并且，令，其中，其中且证明：（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）设不妨设其中，即，由 中产

15、生式 所以综上可得，*1(4)()()L GL G 解：P=S|S1P1SSS|S1P1 证明略。1(5)()()L GL G 解：P=S|S1P1SS|S1P1 证明略。3、设文法 G 有如下产生式：SaBbA AaaSbAA BbbSaBB 证明 L(G)中含有相同个数的 a 和 b，且非空。证：观察发现 A 的产生式 AbAA 中的 bA 可以用 S 来代替，同样 B 的产生式 BaBB 中的aB 也可以用 S 代替。这样原来的文法可以化为如下的形式：SaBbA AaaSSA BbbSSB 进一步地，可以把产生式 AaS 中的 S 代换，把文法化为如下的形式：SaBbA AaaaBabA

16、SA BbbaBbbASB 7设 DFA M=),(0FqQ，证明：对于),(),(,*yxqxyqQqyx 注：采用归纳证明的思路 证明：(周期律 02282067)首先对 y 归纳，对任意 x 来说，|y|=0 时，即 y=根据DFA定义,),(qq),(),(),(),(yxqxqxqxyq,故原式成立。当|y|=n 时，假设原式成立，故当|y|=n+1 时，不妨设 y=wa,|w|=n,|a|=1 根据 DFA 定义aaxqxaq),),(),(，故),(),(),),(),(),(),(yxqwaxqawxqaxwqxwaqxyq原式成立，同理可证，对任意的 y 来说，结论也是成立的

17、。综上所述，原式得证*8证明:对于任意的 DFA M1=(Q,q0,F1)存在 DFA M2=(Q,q0,F2),使得 L(M2)=*L（M1）。证明：（1）构造 M2。设 DFA M1=(Q,q0,F1)取 DFA M2=(Q,q0,QF1)（2）证明 L(M2)=*L（M1）对任意 x*x L(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且

18、中不含形如10110的子串 101100，10，1(4)0,110101x xx和 的倒数第个字符是，且以结尾 0，110，10，10，10，10，100，110，1(5)0,101x xx且 以 开头以 结尾 010，1(6)0,1x xx且 中至少含有两个 1 S0，1110，10，10，1*(7)0,1x xx且如果 以1 结尾，则它的长度为偶数；如果以0 结尾，则它的长度为奇数 S10，10(8)0,1x xx且 的首字符和尾字符相等 00，10，100111(9),0,1 Tx xx 0,100110,1 11.根据给定的 NFA，构造与之等价的 DFA.（1）NFA M1 的状态转

19、移函数如表 3-9 状态说明 状态 输入字符 0 1 2 开始状态 q0 q0,q1 q0,q2 q0,q2 q1 q3,q0 q2 q2 q3,q1 q2,q1 终止状态 q3 q3,q2 q3 q0 解答：状态说明 状态 输入字符 0 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,q2 q0,q1,q2 q0,q1,q3 q0,q1,q2,q3 q0,q1,q2 终止状态 q0,q1,q3 q0,q1,q2,q3 q0,q2,q3 q0,q1,q2 终止状态 q0

20、,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q2 终止状态 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2,q3 q0,q1,q2 q0q0,q1q0,q201,22q0,q1,q3q0,q1,q2q0,q2,q3q0,q1,q2,q30,122001,20210,11 图 3-9 所示 NFA 等价的 DFA 13试给出一个构造方法，对于任意的 NFA),(10111FqQM，构造 NFA 2M),(2022FqQ，使得)()(1*2MLML 注：转化成相应的 DFA 进行处理，然后可参考第 8 题的思路 证明：首先构造一个与 NFA 1M等价的 D

21、FA，3M根据定理（P106），)()(13MLML 构造),(30333FqQM其中 aQpppFpppQppppppFQmmmmQ,.,.,.,|.,2211212121331.),.(.),.(111113mnmnppaqqppaqq 在此基础上2M，,3232 QQ.|.3112FppppFmm 即取所有1M确定化后不是终结状态的状态为2M的终结状态。为了证明)()(3*2MLML，我们在3M的基础上4M),(4044FqQ，其中,3434 QQ44QF，即所有1M确定化后的状态都为终结状态。显然,)(*4ML),(2MLx则20),(Fxq),(),(330MLxFxq又 因 为),

22、(),(),(04030 xqFxqQxq,)(*4ML故x)(3*ML，故)()(3*2MLML 同理容易证明)()(3*2MLML 故)()(3*2MLML，又因为)()(13MLML，故)()(1*2MLML 可知，构造的2M是符合要求的。15P129 15.(1)、（2）（1）根据 NFAM3的状态转移函数，起始状态 q0的闭包为-CLOSURE（q0）=q0,q2。由此对以后每输入一个字符后得到的新状态再做闭包，得到下表：（陶文婧 02282085）状态 0 1 q0,q2 q0,q1，q2 q0,q1，q2，q3 q0,q1，q2 q0,q1，q2，q3 q0,q1，q2，q3 q

23、0,q1，q2，q3 q0,q1，q2，q3 q0,q1，q2，q3 q0=q0,q2，q1=q0,q1，q2，q2=q0,q1，q2，q3，因为q3为终止状态，所以 q2=q0,q1，q2，q3为终止状态 Sq1q2q000，10，1 （2）用上述方法得 状态 0 1 q1,q3 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，q3 q0=q1,q3，q1=q3，q2，q2=q0,q1，q2

24、，q3，q3=q0,q1，q3，q4=q1，q2，q3因为各状态均含有终止状态，所以 q0,q1，q2，q3,q4均为终止状态 1S0q1q2q0q40q310011 注：本题没有必要按照 NFA 到 DFA 转化的方法来做，而且从-NFA 到 NFA 转化时状态没有必要改变，可以完全采用-NFA 中的状态 如（1）状态 0 1 q0(开始状态)q0,q1，q2 q3 q0,q1，q2，q3 q1 q0,q1，q2，q3 q1，q2，q3 q2 q0,q1，q2，q3 q1，q2，q3 q3（终止状态）q0,q1，q2，q3 q0,q1，q2，q3 (2)状态 0 1 q0(开始状态)q1 q

25、2 q3，q0,q1，q2，q3 q1 q2 q1，q2 q2，q2，q3 q0,q2，q3 q3（终止状态）空 q0 16、证明对于的 FA M1=(Q1,1,1,q01,F1)，FA M1=(Q2,2,2,q02,F2)，存在 FA M，使得 L(M)=L(M1)L(M2)证明：不妨设 Q1 与 Q2的交集为空（1）构造 M=（Q1Q2 q0,q0,F）其中：1）=12 F=F1F2 2)(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)，从而有

26、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)F1(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=F1

27、F2 则(q01,x)=1(q01,x)F1 因此 xL(M1)如果是(q02,x)因为 Q1 与 Q2的交集为空 而且（q0,x）F F=F1F2 则(q02,x)=2(q02,x)F1 因此 xL(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 要证 ，

28、只需证明 ，1.证明 ),(20121fqQQM)()()(21MLMLML)()()(21MLMLML)()()(21MLMLML21221121),()(),()(xxxMLxMLxMLMLx使得并且从而有设),(),(),(),(,1201110111111fxqxqaqxqaQqMQxM故对时所以在定义中的状态经过的状态全部都是的过程中在处理)(),(),(),(),(,20122021222MLxfxqxqaqxqaQqMQxM下面证明对时所以在定义中的状态经过的状态全部都是的过程中在处理)()()(21MLMLML 2)再证明 )(),(),(),(),(),(),(),(),()

29、,(22022202212121210112101210101MLxfxqxqxfxfxfxxqxxqxxqxq即得证),(,),(;),(,),(,),(),(),(),(),(.,x,xxx,xxx,),(.,),(),()()()(2202222021101111012202212121010120221011212121021120120121fxqfxqfxqfxqfxqxfxfxxqxqfqMxfqMffqfffMMqMfxqMLxMLMLML说明说明其中即引导到状态从状态将引导到状态从状态将并且使得和后缀的前缀比存在所以移动的必经而且该移动是出发的任何其他移动不存在从外的移动函数

30、式由于除了对应状态转移先到必须要达到状态的定义可知由启动的是从由于即设212121212211()()(,)()()()()()()(MLMLMLMLMLMLMLMLxxxMLxMLx综上所述故从而这表明*（吴丹 02282090）11110112202212121201121218.FA MQq FFA MQqFFA ML ML ML MFADFA MQQqqFaQ,q,paqapa.xL M1 2.1,xx xxkxi ik ，2，2，02证明：对于任意的，存在，使得。证明：不妨将这些看成取，对于，q,p，1设：则其中 121212121212121212121q,pq,pL ML MxL

31、 ML ML ML ML M2xL ML M1 2.1,qpqq,ppq,pL MxL ML ML ML ML ML MLxixixixixx xxkxi ikxixixixixixixi 使得，从而可得设：则其中有，且，从而使得，；，从而可得综合(1)(2)可得2MFADFA。又因为和具有等价性，所以原命题得证。23.FA M 的移动函数定义如下:(q0,3)=q0(q0,1)=q1(q1,0)=q2(q1,1)=q3(q2,0)=q2(q3,1)=q3 其中,q2,q3为终态.(1)M 是 DFA 吗为什么 不是,因为并不是所有的状态,在接收一个字母表中的字符时会有一个状态与之对应.(2)

32、画出相应的 DFA 的状态转移图 31q0q1q2q301011q0,3031,30,1,3(3)给出你所画出的 DFA 的每个状态 q 的 set(q):set(q)=x|x*且(q0,x)=q set(q0)=3*set(q1)=3*1 set(q2)=3*100*set(q3)=3*111*set(q)=(3*0|3*13|3*100*(1|3)|3*111*(0|3)0*1*3*(4)求正则方法 G,使 L(G)=L(M)q03 q0|1 q1 q10 q2|1 q3 q20|0 q2 q31|1 q3 2.理解如下正则表达式，说明它们表示的语言（1）(00+11)+表示的语言特征是

33、0 和 1 都各自成对出现（2）(1+0)*0100+表示的语言特征是以 010 后接连续的 0 结尾（3）(1+01+001)*(+0+00)表示的语言特征是不含连续的 3 个 0（4）(0+1)(0+1)*+(0+1)(0+1)(0+1)*表示所有长度为 3n 或 2m 的 0，1 串（n0,m0）（5）(0+1)(0+1)*(0+1)(0+1)(0+1)*表示所有长度为 3n+2m 的 0，1 串（n0,m0）（6）00+11+（01+10）（00+11）*（10+01）表示的语言特征为长度为偶数 n 的串.当 n=2 时，是 00 或 11 的串。n4 时，是以 01 或 10 开头，中间的子串 00 或 11 成对出现，最后以 10 或 01 结尾的串