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

形式语言与自动机理论试题一、按要求完成下列填空 1. 给出集合,和集合,0,00的幂集 （2x4） (1) , (2) ,0,00,0,00,0,00,0,002. 设=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时，进入陷阱状态） (2) x|x0，1+且x的第十个字符为1 （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） 二、判断（正确的写T，错误的写F） 5x2 1.设和是集合a,b,c,d,e上的二元关系，则 ( T ) 任取(x.,y),其中x,y，使得。 2.对于任一非空集合A， ( T ) 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=rrs（rrs） ( 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分）。 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四、判断语言|n=1是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）解：设L=|n=1。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅依赖于 L的正整数，取Z= 显然，ZL 。 按照泵引理所述，必存在u，v，w。由于|uv|=1，所以v只可能是由0组成的非空串。不妨设v=，k=1 此时有u= ，w= 从而有uvw= 当i=2时，有uvw= 又因为k=1,所以 N+kN 这就是说不属于L， 这与泵引理矛盾。所以，L不是RL。五、构造等价于下图所示DFA的正则表达式。(12分)Sq1q0q2q310001110答案(之一)：( 01+(1+00)(1+00*1)0)*(1+00*1)1) )* (e+(1+00)(1+00*1)0)*00*)q1q0q2q310001110eeXYe预处理：去掉q3：q1q0q21011+00*10eXYe00*去掉q1：q0q21+00(1+00*1)0eXYe00*(1+00*1)101q0eXYe+(1+00)(1+00*1)0)*00*01+(1+00)(1+00*1)0)*(1+00*1)1)去掉q2：去掉q0：XY(01+(1+00)(1+00*1)0)*(1+00*1)1)* (e+(1+00)(1+00*1)0)*00*)六、设M=（，0,1，0,1，B，,B,）,其中的定义如下： （，0）=（，0，R） （，1）=（，1，R） （，0）=（，0，R） （，B）=（，B，R）请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分）解：处理输入串00001000的过程中经历的ID变化序列如下： 00001000 00001000 00001000 00001000 000010000000010000 00001000 00001000 00001000 00001000B 处理输入串10000的过程中经历的ID变化序列如下： 10000 100000 10000 10000 10000 10000 10000B七、根据给定的NFA，构造与之等价的DFA。（14分） NFA M的状态转移函数如下表 状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,q1q2,q1终止状态q3q3,q2q3 q0解答：状态说明状态输入字符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终止状态q0,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, q2参 考 题 目1、设，构造下列语言的文法。 (1) 。 解答：。 (2) 。 解答：。 (3) 。 解答： S aAB|aSAB BAAB aBab bBbb bAba aAaa (4) 。 解答：。 (5) 。 解答：。 (6) 。 解答： 。 (7) 。 解答：。 (8) 。 解答： 。2、给定RG：，试分别构造满足下列要求的RG G，并证明你的结论。解：P=S|S1P1SSS|S1P1证明略。解：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=，证明：对于注：采用归纳证明的思路证明： (周期律02282067)首先对y归纳，对任意x来说，|y| = 0时，即y=根据DFA定义,故原式成立。当|y| = n时，假设原式成立，故当|y|= n+1时，不妨设y = wa, |w| = n, |a| = 1根据DFA定义，故原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证*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 11. 根据给定的NFA，构造与之等价的DFA. （1） NFA M1 的状态转移函数如表3-9状态说明状态输入字符012开始状态q0q0,q1q0,q2q0,q2q1q3,q0q2q2q3,q1q2,q1终止状态q3q3,q2q3 q0解答：状态说明状态输入字符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终止状态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, q2图3-9所示NFA等价的DFA13试给出一个构造方法，对于任意的NFA ，构造NFA ，使得注：转化成相应的DFA进行处理，然后可参考第8题的思路证明： 首先构造一个与NFA 等价的DFA ，根据定理3.1（P106），构造其中在此基础上，即取所有确定化后不是终结状态的状态为的终结状态。为了证明，我们在的基础上，其中，即所有确定化后的状态都为终结状态。显然则又因为故，故同理容易证明故，又因为，故可知，构造的是符合要求的。15 P129 15.(1)、（2）（1）根据NFAM3的状态转移函数，起始状态q0的e闭包为 e-CLOSURE（q0）= q0, q2。由此对以后每输入一个字符后得到的新状态再做e闭包，得到下表： （陶文婧 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为终止状态（2）用上述方法得状态01 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，q3q0= q1, q3，q1= q3，q2，q2= q0, q1，q2，q3，q3= q0, q1，q3，q4= q1，q2，q3因为各状态均含有终止状态，所以q0, q1，q2，q3,q4均为终止状态注：本题没有必要按照NFA到DFA转化的方法来做，而且从e-NFA到NFA转化时状态没有必要改变，可以完全采用e-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 q2 q3， 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)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)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= F1F2 则(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 . 证明：令 ,其中的定义为： 1) 对qQ1-f1，a (q，a)=1(q，a)； 2) 对qQ2-f2，a (q，a)=2(q，a)； 3) (f1，)=q02 要证 ，只需证明 ， 1. 证明 2) 再证明 *（吴丹 02282090）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) 画出相应的DFA的状态转移图(3) 给出你所画出的DFA的每个状态q的set(q):set(q)=x|x*且(q0,x)=qset(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 q1q10 q2|1 q3q20|0 q2q31|1 q32.理解如下正则表达式，说明它们表示的语言（1）(00+11)+表示的语言特征是0和