形式语言与自动机理论-蒋宗礼-参考答案

1、第三章作业答案1已知DFAM1与M2如图3- 18所示。(1) 请分别给出它们在处理字符串(2) 请给出它们的形式描述。(敖雪峰 02282068)1011001的过程中经过的状态序列。图3- 18两个不同的DFAqoq3qiq3q2q3qiq3；解答:(1)M1在处理1011001的过程屮经过的状态序列为M2在处理1011001的过程中经过的状态序列为qq2q3qiq3q2q3qi；考虑到用形式语言表示，用自然语言似乎不是那么容易, 所以用图上作业法把它们用正则 表达式来描述M1: 01 +(00+1 )(11 +0)11 +(10+0)(11 +0)*M2: (01 + 1+000)(01

2、 )*+(001 + 11)(01 + 1 +000)*(陶文嬪 02282085 )2. 构造下列语言的DFA(D 0, 1(3) x|x 0, 1但X中不含00的串(设置一个陷阱状态，一旦发现有 00的子串，就进入陷阱状态)(4) x|x 0 , 1沮x中不含00的串(可接受空字符串，所以初始状态也是接受状态)x|xA0, 1但x中不含形如10110的子串(设置一个陷阱状态，一旦发现有 00的子串，就进入陷阱状态)(7)x|x0, 1但当把x看成二进制时，x模5和3同余，要求当x为0时,|x|=1,_ax=0时,x的首字符为11.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入

3、的符号为0,则进入陷阱状态2.设置7个状态：开始状态qs,q。：除以5余0的等价类，除以5余1的等价类口 2：除以5 余2的等价类，q3：除以5余3的等价类，q4：除以5余4的等价类，接受状态qt3.状态转移表为状态01qoqiq2qiqaq2Q2qoq4q3qiq2q4q3q4(8) x|x0, 1但x的第十个字符为10,进入陷阱状态)(设置一个陷阱状态，一旦发现x的第十个字符为(9) x|x 0, 1且x以0开头以1结尾(设置陷阱状态，当第一个字符为1时，进入陷阱状态)(10) x|x 0, 1且x中至少含有两个10x以0结尾，则它的长度(11) x|x0, 1且如果x以1结尾，则它的长度

4、为偶数；如果 为奇数可将0,甘的字符串分为4个等价类。qo：的等价类，对应的状态为终止状态qi： x的长度为奇且以q2： x的长度为奇且以0结尾的等价类q3： x的长度为偶且 1结尾的等价类以0结尾的等价类q4： X的长度为偶且以1结尾的等价类(12)x|x是十进制非负数(13) ns OO(14) (张友坤 02282061)3(1)00,1Set(q0)=x lx-50,1Set(q0)=；Set(q1)=x | x- - *(3)-=0,1Set(q0)=；Set(q1)=x并且x中不含形如Set(q2)=x |x-并且x中不含形如00的子串00的子串00的子串00的子串Set(q0)=

5、x | x匚-*并且x中不含形如Set(q1)=x | x 并且x中不含形如*=0,1*Set(q0)= x|，并且0或者x中含形如100的子串Set(q1)=x | x三*,并且x中含形如1的子串Set(q2)=x | x 二，并且x中含形如10的子串Set(q3)=x | xr,并且x中含形如101的子串Set(q4)=x| X-,并且x中含形如1011的子串Set(q5)=x| X-,并且x中含形如10110的子串0,1Set(q0)= ； +Set(q1)=x | x0 Set(q2)=x | x-,并且x中不含形如10110的子串而且x中含有1Set(q3)=x | X-,并且x中不

6、含形如10110的子串而且x屮含有1(7)0=0,1 Set(qs)= Set(qe)= 0Set(q1)=x | x, +,并且把x看成二进制数时，X% 5=1Set(q2)=x | X；，并且把x看成二进制数时，X% 5=2Set(q3)=x |Set(q4)=x |x 7 ,并且把x看成二进制数时，x% 5=3x三7 +,并且把x看成二进制数时，X% 5=4Set(q0)=x |(8)M=Q, *x三7 +,并且把x看成二进制数时，X% 5=0并且x不为0Q=q o,qi,q2, qo =0,1当0=i0AA 1S | 1S 1BB OS | 0将代入SOA； 06,代入SB得S01S|

7、01S 1 OS | 1 0由此可以看出该文法接受的语言为L=（10|01） *，显然01或10分别是作为整体出现的,所以L（M）中0和1的个数相等。7设 DFAM=（Q,、，、，q。，F）,证明：对于-X,y二 *,q Q,、.（q,xy） =、. C （q,x）, y）注：采用归纳证明的思路证明：（周期律02282067）首先对y归纳，对任意x来说，|y| = 0时，即y=；根据 DFA 定义、（q,；）二口八（q,xy）=、（q,x） =.（. （q, x）, ；）=、（、（q,x）, y）,故原式 成立。当|y| = n时，假设原式成立，故当|y|=n+1时，不妨设 y = wa, |

8、w| = n, |a| = 1根据 DFA 定义、（q , xa ）二、.（、.（q , x）, a）, a ,故、(q,xy)二、(q,xwa)二、(q,xw),a)二、(q,x), w),a)二、(、(q, x), wa)二 G (q, x), y)原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证& 证明:对于任意的 DFAMi=(QQ,S,qFi)存在 DFA M 2=(QQ , S ,q,F2),(冯蕊 02282075)使得 L(M 2)=I 一 L ( MJ o证明：(1)构造M2。设 DFAM 1=(Q,I,S ,qo,Fi)取 DFA M 2=(Q,工,S

9、 ,qo,Q Fi)(2)证明 L(M2)=工一L ( Mi)对任意x工*=工并且x -x- L(M 2)=工一L ( Mi) ： = S (q,x) Q FA S (q,x):二 Q 并且 S (q,x) Fi 二 x： L(M i)=x,工 一 L ( Mi)9. 对于任意的DFA Mi=(Qi,刀,S i,qoi,Fi)，请构造DFA Mg,刀,S 2牛尸2),使得L(M i)=L(M 2)To 其中 L(M)T=X|XT L(M)(褚颖娜 02282072)构造 s -NFA M 使得 L(M)=L(M 1)取NFA M=( Q,刀,S , q。q o)其41) Q= QiU q ,

10、q * Qi2) 对于- q,p Qi,aE,如果 Si(q,a)=p,q S (p,a)3) S (q。, e )= Fi(2) 证明：L(M)=L(M i)T对- x=aia2-am L(M)qo ai a2 am 卜qfaia2am 卜a qia2am卜aia2 q2am 卜ai a2qm-i am卜 aa2 amqoi其中 qt S (qo, J, qi% as), qsg, a2), qOism-i, am)并且 qz贝g S i(qoi, am)= qm-i, S i(qm-i, am-i)= qm-2,*S i(q2, S2)= qiS i(qi, ai)= qf因止匕 Qoi

11、am am-i ai 卜 am qm-i am-i.ai b am 3m-i -q2 S2 Si b am am-i-a2 qiSi卜 am am-i -a2 aiqf因此 am am-i ai L(M i)即 xT L(M i)同理可证对于 x=aia2-am L(M i) xT=am am-i ai L(M i)L(M)=L(M i)T 得证(3) 将e-NFA M确定化首先构造与 e-NFA M=( Q,刀,S , q, qi)等价的 NFA M 3=( Q,刀,S 2, q, qi)其中对于 一 (q,a)eCT 刀 S2(q,a)=SJ(q,a)然后按照以前学过的方法构造与NFA M

12、 3=( Q, E ,S 2, q, qi)等价的DFAMi=(Qi,E,S i,qo,Fi)其中:Qi=2Q Fi= qoisi(qi,q2,，qn,a)=pi,p2,pn当且仅当 S2(q i,q2 ,，qn,a)= p i,p2,pn *AA注：此题(io题)张友坤、吴玉涵所做完全一样！iO、构造识别下列语言的NFA(吴玉涵02282091)(i) x x 0,i +且x中不含形如00的子串(2) X x0,1且x中含形如10110的子串(3) xxA0,1 +且x中不含形如10110的子串0. 10. 1(4) X A0,r和X的倒数第10个字符是X且以01结尾(5) x xA0,1

13、+且x以0开头以1结0, 101(6) x xA0,1 +且x中至少含有两个10. 10. 10. 1xxA0,1但如果x以1结尾，则它的长度为偶数；如果以0结尾，则它的长度为奇数1(8) xxA0,1+且X的首字符和尾字符相等0. 11(9) xcoxTx,/k0,11这是最基本的单元，其他的可以通过这个逐级构造岀来，以满足题目要求。it*11.等价的DFA.根据给定的NFA,构造与之(吴丹 02282090)(1) NFAMi的状态转移函数如表3-9状态说明状态输入字符012开始状态qoqO,q1q0,q2q0,q2qiq3,q00q2q20q3,q1q2,q1终止状态q3q3,q2q3q

14、0解答:状态说明状态输入字符012开始状态q0qO,q1q0,q2q0,q2qO,q1q0,q1,q3q0,q2q0,q2q0,q2qo,qiq0,q1,q2,q3q0,q1,q2q0,q1,q2q0,q1,q3q0,q1,q2,q3q0,q1,q2终止状态q0,q1,q3q0,q1,q2,q3qO, 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,q2qO,q1 qo,qi,q3 q0,q2,q310122o011,2 厂、0,12 3,q,F3),

15、其中Qa =2QI,F3 = PI3P2.Pm |pi, P2.PmQ, Pi , P.Pm Fi =,、3(qi.qn,a)ziPiPm=、i (q.qn, a)r. Pi.Pm在此基础上 M2，Q2 =Q3j 2= 3jF2 = PiPm |Pi Prn F3 二即取所有Mi确定化后不是终结状态的状态为M?的终结状态。为了证明L(M2)二a *丄(M3),我们在M3的基础上M4= (Q4,；4,q,F4),其中Q4二Q3,、： 4= , F4 = Q4,即所有Mi确定化后的状态都为终结状态。显然L(M4)八XL(M2),则、(q,x)F“二(q,x) F3厂二XL(M3),又因为(q0,x

16、) Q3二(q,x) F4二、(q,x)L(M r,故 x、*-L(M3),故L(M2)丄M)同理容易证明L(M2) = 7 (f r；),x2)-，(q02 * X2J= 202 *2)7即得证xL(M)2)再证明L(M) L(M!)L(M2)设xL(M),即、(qi,x) =f2由于M是从qi启动的，由M的定义可知,M要达到状态怯必须 先到由于除了对应状态转移函数式;(fiJ = q02的移动夕卜，不存 在从仏出发的任何其他移动，而且该移动是的必经 移动,所以， 比存在X的前缀Xi和后缀X2,使得咲议2,并且Xi将M从状态qoi引导 到状态fi,x?将M从状态q02引导到状态f2即、(qo

17、,x)二、1,皿)=s(fi,X2)冷)=6 (q x )这表明xL(M JX4(M2)从而 x = XjX2 L(M OL(M 2)故 L(M) L(Mi)L(M2)综上所述，L(MaL(Mi)L(M2if*(吴丹 02282090)18证明:对于任意的 FAML(QJZ； ,qoi,),FA M2=( Qzg 2,2002,& ) 存在 FAM,使得 LM= LMa|LM2o证明：不妨将这些FA看成DFA取M 二 Q1 Q29 c, r, qoi, q。？ , F对于-a : 工 H2, q, P 卢 Q,、q,p , a= nq, a ,学 p, a .1 设：x L M 贝I x=x1

18、x2xk 其中 xi i1,ki_ 二 Pr2使得q,p, xi = Tq, xi A 2 P, xi.xi LMi riLMzhX LMjILM?从而可得L M L Mi Dl M22 设：x L Mi IT M2 贝 vx =x1x2xk其中 xi i 1,k l二 I有q, xi且：2P, xi从而使得、1 q, xi Iqp, xi ；2p, xiq,p 1, xixi L M = x L M从而可得LM1PILM2LM综合(2)可得LM= L MjlL M2 O又因为FA和DFA具有等价性，所以原命题得证。19、总结本章定义的所有FA,归纳出它们的特点，指出它们之间的差别。(吴玉涵0

19、2282091)本章学习了 DFA, NFA, NFA, 2DFA和2NFA所有的FA都是一个五元组(Q, 2, S, q0, F)最大的区别就是状态转移函数S对于DFA,字母表中的每个字母都有唯一确定的状态转移函数。也就是说X2, q Q, a2只有唯一确定的状态。一 3(q,a)Q对于NFA,对于字母表中的每个输入字符可以有不同的状态转移，对于身的移动。串，是一个到自对于NFA,是指在不接受任何字符的情况下，自动机的状态可以发身转移。对于2DFA ,对于字母表屮的每个字符，对于每个状态都有唯一的状态转移，即- 3 (q, a) Q X2, q Q, a2只有唯一确定的状态。与DFA不同的是

20、，2DFA的读头可以在一次 状态转移中不移动，或者回退一个，或者向下读一个。对于2NFA ,与2DFA相似，但是并不是对于字母表屮的每个输入字符都有转移函数，2NFA与2DFA的区别类似于DFA与NFA的区别。20构造如图320所个的DFA对应的右线性文法。(周期律02282067)对图1：构造文法G= (V, T, P, S),其中V=S, A, B, C, T=1 , 0S0A|1|1CA0S|1|1CP：B0|0C |1SC0A|1A对图2:构造文法G= (V, T, P, S),其屮V=S, A, B, C, T=1 , 0S0A|1BA 1S|1|0BP：B0C |0|1AC0A|1

21、A*祜 *祜 *衬*衬 *桂*桂*吴贤毘02282047)21 .构造下图所示DFA对应的左线性文法。图形如下所示解：设q。、 由于q2 为不可 达状 态，故 先去掉 该状 态。S A1 | B1 10q2q3q 1、q2、q3所对应的字符分別为A、B、G得到该图所对应的左线性文法为:4 G0| G1 AO 0LBO图形如下所示:1设该状C、Do解：图屮有多个终结状态，为方便起见，增加一个终结状态（红色表示）态所对 应的字符为G又设q、q2、q3所对应的字符分别为人则该图所对应的左 线性文法为：A C0| BO | &“ COSBO| A1 1 B C1 DO | D1 AO | 0AT B1

22、22. 根据（敖雪峰02282068）下列给定文法，构造相应的FA(1)文法G1的产生式集合如下:G1: ST a|AaA T a|Aa|cA|BbA T a|Aa|Ac|BbBTa|b|c|Ba|Bb|Bc解答：文法G1对应的FA如下所示Bz a,b,c 丿文法G2对应的必如下所示a,b,c(冯蕊 02282075)23. FA M的移动函数定义如下3 (qo,3)=q 03(q,1)=q 13q,0)=q 23qi,1)=q 33(q2,0)=q 23(q3,i)=q 3其中,q2,q3为终态.M是DFA吗？为什么？不是，因为并不是所有的状态(2)画出相应的DFA的状态转移图在接收一个字对

23、农屮的字符时会有一个状态与乙对应qi3101/(qOl33、0、0,3 1-1(qOBOV一 11,30,1,3给出你所画出的 DFA的每个状态q的set(q):set(q)=x|x 工且3 (q,x)=q set(qo)=3 set(qi)=3 1set(q2)= 3*100*set(q3)= 3*111*set(q)=( 3 0|3 13|3 100 (113)|3 111 a的产生式，增加一个开始状态乙使得q。二Z所以E=F,对于产生式B、Aa,则有、(A,a)=B,对于产生式：B a,且E是开始状态，则有、：(E,a)二B.下面证明G(E)与FA等价，即证明L(G(E)=L(M)不会:

24、)2)根据FA M =(Q；,、，q0,F),构造相应的G(E)为了方便起见，在根据给定的FA构造等价的左线性文法的之前，先对 FA做如下的处理：1. 删除FA的陷阱状态。2. 在FA中增加一个识别状态3. “复制” 一条原来到达终止状态的弧，使它从原来的起点出发，到达新添 加的 识别状态。相应的文法的构造依照如下两条进行：1. 如果、:(A,a)Zl B,则有产生式Ba2. 如果且A是开始状态qa，则有产生式B a。*?|O|C*J|O|O|C*3|O|O|O|C*3|O|O|C* 林*林* 林* 林 *林(吴丹 02282090)26. 证明定理3-6o ( 2DFA与FA等价)证明：对于

25、2DFAM是一个五元组M二Q, ,:, q. , F其中，Q, , q。，F的意义同与DFAo、： Q :二一；QL, R, S?,对于一 q, a 三 Q1如果心(q, a二!p, L/表示在读入a从状态q转移到状态p,并将 读头向左移动，指 向输入字符的前一个字符。2如果心(q, a二：p, R 表示在读入a从状态q转移到状态p,并将 读头向右移动，指 向输入字符的下一个字符。3如果心(q, a二Ip, 9表示在读入a从状态q转移到状态p,读头 保持在原位置不 动。我们构造与之等价的FA27. 证明定理3-7(周期律02282067)证明：因为FA是一-种特殊的2NFA,他是当qQ,a7时

26、，都有、；(q,a) = ( D)(Pm,D)，此时的D只为往右移动，即一个每一个状态读入一个字符后读头都往右移动指向下一字符的2NFA,故对任意的FA,定会找到一个与之等 价的2NFA与之对应。因此我们只需要证明对任何的2NFA M 1 =(Q.,： r, Fi,q。)，都存在FAM 2= (Q2/2, F2, q。)与之等价。对于任何的 2NFA Mi =(Qi, 、. “ Fi, q。)，构造 FA M2 =(Q2，、2,F2,q。),按三个方式构造：2：1 如果 q Qa ,、i(q,a)二p, R,则、2(q,a)二 p ；2如果 q Qi,a : -二、i(q,a)zi p,S,则如果、i(p,a匚o, R,则、2(q,a) =0 ；如果r ( p, a) =o, S,则重复第二步；如果r(p,a) o, L,则对于集合 A = r|b、j(r,b) = (o,R),、2(q,a)二 r,r