形式语言与自动机理论

第三章作业答案1.已知DFAM1与M2如图3—18所示。(敖雪峰02282068)请分别给出它们在处理字符串1011001的过程中经过的状态序列。请给出它们的形式描述。S0S0图3—18两个不同的DFA解答：(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3;M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;(2)考虑到用形式语言表示，用自然语言似乎不是那么容易，所以用图上作业法把它们用正则表达式来描述：M1:[01+(00+1)(11+0)][11+(10+0)(11+0)]*M2:(01+1+000){(01)*+[(001+11)(01+1+000)]*}个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个2.构造下列语言的DFA(1)(陶文婧02282085)(2){0,1}*0,1{0，1}+(2.构造下列语言的DFA(1)(陶文婧02282085)(2){0,1}*0,1{0，1}+S（4）{xlxe{0,1}*且x中不含00的串}（可接受空字符串，所以初始状态也是接受状态）SSS1（5）{xlxe{0，1}+且x中含形如10110的子串}0（6）{xlxe{0，1}+且x中不含形如10110的子串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）1（7）{xlxe{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，凤=1,且x^0时，x的首字符为1}1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态2.设置7个状态：开始状态qs,q0.除以5余0的等价类，％除以5余1的等价类,q2.除以5余2的等价类，q3.除以5余3的等价类，q4.除以5余4的等价类，接受状态qt（8）（xlxe{0,1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0,进入陷阱状态）厂、厂、厂、s厂、cST山马叫马04马vvUAJ（9）{xlxe{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）SS（10）{xlxe{0，1}+且x中至少含有两个1}则它的长度（11）{xlxe{0,1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，为奇数}可将{0，1}+的字符串分为4个等价类。则它的长度q0国的等价类，对应的状态为终止状态q1：x的长度为奇且以0结尾的等价类q2x的长度为奇且以1结尾的等价类q3：x的长度为偶且以0结尾的等价类q4：x的长度为偶且以1结尾的等价类S（12）{xlx是十进制非负数}5，6，7，8，9（13）中S（14）£S&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个

(张友坤02282061)3⑴10Z={o,i}Set(q0)={xIxGZ*}(2)Z={o,i}S（12）{xlx是十进制非负数}5，6，7，8，9（13）中S（14）£S&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个(张友坤02282061)3⑴10Z={o,i}Set(q0)={xIxGZ*}(2)Z={o,i}Set(q0)=eSet(ql)={xIxGZ+}(3)Z={o,i}Set(q0)=eSet(ql)={xIxeZ+并且x中不含形如00的子串}Set(q2)={xIxeZ+并且x中不含形如00的子串}⑷nZ={O,1}Set(q0)=(xSet(ql)={x11xexeZ*,并且x6｛0｝*或者x中含形如100的子串｝Z*,并且X中含形如1的子串｝Set(q2)={x1xeZ*,并且x中含形如10的子串｝Set(q3)={x1xeZ*,并且x中含形如101的子串｝Set(q4)={x1xeZ*,并且x中含形如1011的子串｝Set(q5)=(x1xeZ*,并且x中含形如10110的子串｝(6)Z={O,1}Set(qO)={S)Set(ql)=(xIxg{0+}}Set(q2)={xIxeZ*,并且x中不含形如10110的子串而且x中含有1}Set(q3)={xIxeZ*,并且x中不含形如10110的子串而且x中含有1}(7)0Z={o,i}Set(qs)={8}Set(qe)={0}Set(ql)=(xIx€Z+,并且把x看成二进制数时，x%5=1)Set(q2)={xIxeZ+,并且把x看成二进制数时，x%5=2}Set(q3)={xIxeE+,并且把x看成二进制数时，x%5=3}Set(q4)={xIxeZ+,并且把x看成二进制数时，x%5=4}Set(q0)={xIxeE+,并且把x看成二进制数时，x%5=0并且x不为0}(8)M={Q,E,§,q0,F}。={%月1月2，・・％}E={0,1}当0<=i<=8时候，§(q「0)=§(qi^Fi+D§(q9,1)=q10§(q1o，0)=§(q10,1)=q10F={q10}Set(q0)={8}Set(q1)={0,1}Set(q2)={x|xeE+,并且1x1=2}Set(q3)={x|xeE+,并且1x1=3}Set(q4)={x|xeE+,并且1x1=4}Set(q5)={x|xeE+,并且|x|=5}Set(q6)={x|xeE+,并且|x|=6}Set(q7)={x|xeE+,并且|x|=7}Set(q8)={x|xeE+,并且|x|=8}Set(q9)={x|xeE+,并且|x|=9}Set(q10)={x|xeE+,并且x的第十个字符是1}⑼M={Q,E,§,q0,F}Q={q0,q1,q2}E={0,1}§(q0,0)=q1§(q1,0)=q1§(q1,1)=q2§(q2，1)=q2§(q2，0)=q1F={q?}Set(q0)={8}Set(q1)={x|xeE+,并且x以0开头以0结尾}Set(q2)={x|xeE+,并且x以0开头以1结尾}(10)M={Q,E,§,q0,F}Q={q0,q1,q2}E={0,1}§(q0,0)=q0§(q0,1)=q1§(q1,0)=q18(qi」)=q28(q拱片q28(q2,0)=q2F={q2)Set(q0)={0}*Set(q1)={xIxeE+,并且x中只有一个1}Set(q2)={xIxeZ+,并且x至少有俩个1}M={Q,1,8,q0,F}Q={q0,q1,q2,q3,q4}E={0,1}8(q0,0)=q18(q0,1)=q48(q1,0)=q38(q1,1)=q28(q2,1)=q48(q2,0)=q18(q3,0)=q18(q3,1)=q48(q4,1)=q28(q4,0)=q3F={q0,q1,q2}Set(q0)={8}Set(q1)={x|xeE+,以0结尾，长度为奇数}Set(q2)={x|xeE+,以1结尾，长度为偶数}Set(q3)={x|xeE+,以0结尾，长度为偶数}Set(q4)={x|xeE+,以1结尾，长度为奇数}(12)M={Q,E,8,q0,F}Q={q0,q1,q2,q3,q4}E={.,0,1,2,...,9}F={q1,q2,q4}8(q0,0)=q18(q0,1|2|3|4|5|6|7|8|9)=q28(q1,.)=q28(q2,0|1|2|3|4|5|6|7|8|9)=q28(q2,.)=q38(q3,0|1|2|3|4|5|6|7|8|9)=q48(q4,0|1|2|3|4|5|6|7|8|9)=q4Set(q0)={8}Set(q1)={0}Set(q2)={十进制正整数}Set(q3)={十进制非负整数后面接个小数点.}Set(q4)={十进制正小数}(13)Set(q0)={8}Set(q0)=0(14)Set(q0)={8}个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个4在例3-6中，状态采用q［aa...a］的形式，它比较清楚地表达出该状态所对应的记忆内12n容，给我们解决此问题带来了很大的方便，我们是否可以直接用［%a2...。〃］代替q［aa...a］呢？如果能，为什么？如果不能，又是为什么？从此问题的讨论，你能总12n结出什么来？(唐明珠02282084)答：我认为能够直接用［aa...a］代替q［aa...a］，因为在例3-6中，q［aa...a］只是一12n12n12n种新的表示方法，用来表示状态存储的字符，这样就省去了在8中逐一给出每一个具体的输入字符和状态的定义。它的作用在于使FA中状态定义更加简洁。得到结论：在今后描述FA时，应该根据具体的情况，使用适当的方法。*******************************************************************************试区别FA中的陷阱状态和不可达状态。(吴贤珺02282047)解：⑴陷阱状态(课本97页)：指在其它状态下发现输入串不可能是该FA所识别的句子时所进入的状态。FA一旦进入该状态，就无法离开，并在此状态下，读完输入串中剩余的字符。⑵不可达状态(课本108页)：指从FA的开始状态出发，不可能到达的状态。就FA的状态转移图来说，就是不存在从开始状态对应的顶点出发，到达该状态对应顶点的路径。⑶从两者的定义可见：相对于不可达状态来说，陷阱状态是可达的。但是，它们都是状态转移图中的非正常状态。如果从状态转移图中的状态引一条弧到不可达状态，同时不可达状态所有的移动都是到自身。这样，不可达状态就变成了陷阱状态。力$$$$$$$$$$$$$$$$$力、******************************************************************************注：此题目有问题，可以将题设改为：X中0和1个数相等且交替出现证明：题目有不严密之处，图中给出DFA与题目中的语言L(M)={x|xx』0，1}+且x中0的个数和1的个数相等}不完全对应，首先图中的DFA可接受空字符串，而L(M)不接受，其次，对于有些句子，例如1100，L(M)可以接受，但DFA不接受根据图中的DFA可看出，右下角的状态为陷阱状态，所以去除陷阱状态由DFA可构造出与其对应的右线性文法：(刘钰02282083)ST0AAT1S11ST1BBT0S10将1S,1代入5T0A；0S,0代入5T1B得ST01S101ST10S110由此可以看出该文法接受的语言为L={(10I01)*},显然01或10分别是作为整体出现的，所以L(M)中0和1的个数相等。““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““******************************************************************************设DFAM=(0E,5,q0,F)，证明：对于Vx,ye^*,qeQ,5(q,xy)=8(6(q,x),y)注：采用归纳证明的思路证明：(周期律02282067)首先对y归纳，对任意x来说，IyI=0时，即y=e根据DFA定义6(q,S)=q,6(q,xy)=6(q,x)=6(6(q,x),8)=6(6(q,x),y)做原式成立。当IyI=n时，假设原式成立，故当IyI=n+1时，不妨设y=wa,IwI=n,IaI=1根据DFA定义6(q,xa)=6(6(q,x),a),ae£，故6(q,xy)=6(q,xwa)=6(6(q,xw),a)=6(6(6(q,x),w),a)=6(6(q,x),wa)=6(6(q,x),y)原式成立，同理可证，对任意的y来说，结论也是成立的。综上所述，原式得证“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************证明:对于任意的DFAM1=(Q,£,&,q0,F1)存在DFAM2=(Q,£,&,q0,F2),(冯蕊02282075)使得L(M2)=£*—L(MJ。证明：(1)构造m2。设DFAM1=(Q,£,5,q0,F1)取DFAM2=(Q,£,5,q0,Q—F1)(2)证明L(M2)=£*—L(M1)对任意xe£*xeL(M2)=£*—L(M1)05(q,x)eQ—F]05(q,x)eQ并且5(q,x)wF]0xe£*并且xwL(M]Qxe£*—L(M1)“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************对于任意的DFAM]_(Q],E,51,q01,F1),请构造DFAM1=(Q2,E,52,q02,F2)，使得L(M])=L(M2)t。其中L(M)t={xIxtEL(M)}(褚颖娜02282072)(1)构造8-NFAM使得L(M)=L(M1)取8-NFAM=(Q,E,5,q0,{q01})其中：1)Q=Q1U{q0},q0wQ12)对于Vq,p£Qi,aeE,如果51(q,a)=p,qE5(p,a)3)5(qo,£)=Fi证明：L(M)=L(M1)T对Vx=a1a2...amEL(M)q°ai%...amEaia2...amES支…amE%42-・amI■…E%%-&卜ai%•••%q01其中qfE5(q0,顷qi^5(qf,ajq2^5(qi,a2),.qoie5(qm-i,am)并且qfGFI则5i(q°i，am)=qm-i，5i(qm-i，am-i)=4皿-2，・••5iW，%)=S5i%诺=4f因此qoiamam-i-aiIamqm-i弟…K%日2%%K%..%"iIamam-i...%aiqf因此amam-i...aiEL(Mi)即xtGL(Mi)同理可证对于Vx=aia2.amEL(Mi)xT=amami.ai^L(Mi)L(M)=L(M])t得证将£-NFAM确定化首先构造与£-NFAM=(Q，E，5,qo，(q0i})等价的NFAM3=(Q，E，52，q0，(q0i})其中对于V(q,a)EQ*工52(q,a)=5人(q,a)然后按照以前学过的方法构造与NFAM3=(Q,E,52,q0,{q0i})等价的DFAMi=(Qi,E,5i,[q0],Fi)其中：Q]=2qFi={q0i}5i([qi,q2,.,qn],a)=[pi,p2,.,pn]当且仅当52({qi,q2,.,qn},a)={pi,p2,.,pn}*******************************************************************************注：此题(10题)张友坤、吴玉涵所做完全一样！！i0、构造识别下列语言的NFA(吴玉涵0228209i)(i){x|xe{0,i}+且尤中不含形如00的子串}ii

(2){xxe{0,1}+且尤中含形如10110的子串}0,1⑶{xxe{0,1}+且尤中不含形如10110的子串}{xxe{0,1}+和尤的倒数第10个字符是1,且以01结尾}0,1J—10，10，10，1

oooo0，1100101010”'{xxe{0,1}+且尤以0开头以1结尾}(6){xxe{0,1}+且尤中至少含有两个1}0，10，10，1(7){xxe{0,1}*且如果尤以1结尾，则它的长度为偶数;如果以0结尾，则它的长度为奇数}

（8）{xxe{0,1}+且尤的首字符和尾字符相等}(9){仙xtx,①e{0,1}+}0,10,1这是最基本的单元，其他的可以通过这个逐级构造出来，以满足题目要求。个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个11.根据给定的NFA，构造与之等价的DFA,（吴丹02282090）（1）NFAM的状态转移函数如表3-9状态说明状态输入字符012开始状态q0{q0,q1}{q0,q2}{q0,q2}q1{q3,q0}0{q2}q20{q3,q1}{q2,q1}终止状态q3{q3,q2}{q3}{q0}

解答:状态说明状态输入字符012开始状态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,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]q00•:•120,41,220,1[q0,q2]1,q2]2q00•:•120,41,220,1[q0,q2]1,q2]2100,1[q0,q1,q2,q3]♦2图3-9所示NFA等价的DFA(2)NFAM2的状态转移函数如表3-10状态说明-状态输入字符012开始状态q0{q1,q3}{q1}{q0}q1{q2}{q1,q2}{q1}q2{q3,q2}{q0}{q2}终止状态q3{q0}{q3}解答:状态说明状态输入字符012开始状态q0[q1,q3][q1][q0][q1,q3][q2][q0,q1,q2][q1,q3]

[q1][q2][q1,q2][q1][q2][q2,q3][q0][q2][q0,q1,q2][q1,q2,q3][q0,q1,q2][q0,q1,q2][q1,q2][q2,q3][q0,q1,q2][q1,q2]终止状态[q2,q3][q2,q3][q0][q2,q3]终止状态[q1,q2,q3][q2,q3][q0,q1,q2][q1,q2,q3][q0,q1,q2][q1,q3]212100[q2]20「[q2,q3]011[q1]'、.1•J002[q3,q1,q2]20图3-10所示NFA等价的DFAe力力力$$$$$$$$$$$$$$$$$力、mi，+++++++++++++个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个12.证明对于任意的NFA,存在与之等价的NFA,该NFA最多只有一个终止状态(刘钰02282083)证明：对于任意的NFAM=(Q,E,S,q0,F)，我们如果能构造出一个只有一个终止状态的NFA,并且与之等价，即可证明上面的定理而对于任意的NFA存在下面两种情况：终止状态只有一个终止状态有多个要构造这个等价的NFA,可以采用如下方法：对(1)无需变化，该NFA即为满足条件的NFA对(2)可以在该NFA的状态图上添加一个新的终止状态，并将原来的多个终止状态所连接的弧复制到该状态上，此时这个终止状态为新状态图中唯一的终止状态，且这个新的NFA与原NFA等价，满足条件我们总能构造出这样的NFA因此对于任意的NFA，存在与之等价的NFA,该NFA最多只有一个终止状态&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个13.试给出一个构造方法，对于任意的NFAM=(Q,Z,5,q,F)，构造NFA11101M=(Q,Z,5,q,F)，使得L(M)=Z*-L(M)2220221注：转化成相应的DFA进行处理，然后可参考第8题的思路

证明:(周期律02282067)首先构造一个与NFA吃等价的DFA,吃根据定理3.1(P106),顷「"(吃)构造M=(Q,Z,5,[q],F),其中33303Q=2Q1，F={[证明:(周期律02282067)首先构造一个与NFA吃等价的DFA,吃根据定理3.1(P106),顷「"(吃)构造M=(Q,Z,5,[q],F),其中33303Q=2Q1，F={[p,p...p]I{p,p...p}cQ,{p,p...p}nF林},{p,p...p}cQ,a”3312m12m12m112m5([q...q],a)=[p...p]。5({q...q},a)={p...p}

31n1m11n1m在此基础上M，Q=Q,5=5,F={[p...p]I[p...p]nFM}2232321m1m3即取所有M1确定化后不是终结状态的状态为M2的终结状态。为了证明L(M)二£*-L(M)，我们在M的基础上M=(Q,Z,5,q,F)，其23344404中Q4=Q3,54="F4=Q4，即所有M1确定化后的状态都为终结状态。显然L(M4)=£*,n5(q0,x)PlF3w©nx冬L(M3),又因5(q,x)eQn5(q,x)eFn5(q,x)eL(M)=£*,故xe£*-L(M)，VxeL(M2),则5(q0,XF2州-L(M3)同理容易证明L(M2)目£-L(M3)故L(M2)=£*-L(M3)可知，构造的M2是符合要求的。“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************14.构造识别下列语言的8-NFA。(吴贤珺02282047)⑴{x|xE{0,1}+且x中含形如10110的子串}U{x|xE{0,1}+和x的倒数第10个字符是1，且以01结尾}。解：得到的e-NFA如下所示：eS⑵{x|xE{0,1}+且x中含形如10110的子串}{x|xE{0,1}+和x的倒数第10个字符是1,且以01结尾}解：得到的e-NFA如下所示：S0,1—O⑶{x|xE{0,1}+且x中不含形如10110的子串}U{x|xE{0,1}+且x以0开头以1结尾}。S0,1—O解：关键是构造第一个FA，方法是设置5个状态：q0：表示开始状态，以及连续出现了两个以上的0时所进入的状态。q1：表示q0状态下接受到1时（即开始状态或2个以上的0后输入1时）所进入的状态。q2：表示％状态下接受到0时（即开始状态或2个以上的0后输入10时）所进入的状态。q3：表示q2状态下接受到1时（即开始状态或2个以上的0后输入101时）所进入的状态。q4：表示q3状态下接受到1时（即开始状态或2个以上的0后输入1011时）所进入的状态。故得到的e-NFA如下所示：

⑷{x|xE{0,1}+且x中不含形如00的子串}{x|xE{0,1}+且x中不含形如11的子串}。解：得到的e-NFA如下所示：另外，本题可以构造DFA如下（其中qt为陷阱状态）:

⑸{x|xE{0,1}+且x中不含形如00的子串}C{x|xE{0,1}+且x中不含形如11的子串}。解：由于x中既不含形如00的子串，又不含形如11的子串，故x中只能是01相间的串。所以，得到的8-NFA如下所示:另外，本题可以构造DFA如下(其中q+为陷阱状态):个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个15.(1)根据NFAM3的状态转移函数，起始状态q0的£闭包为^-CLOSURE(q0)={q0q2}。由此对以后每输入一个字符后得到的新状态再做£闭包，得到下表：(陶文婧02282085)状态01{q0q2}{q0q】q2}{q0q1q2q3}{q0q1q2}{q0q1q2q3}{q0q】q2q3}{q0q,q2q3}{q0q]q2q3}{q0q】q2q3}q0={q0q2}，q1={q0q1q2}，q2={q0q1q2q3}，因为q3为终止状态，所以q2={q0q1q2q3}为终止状态’’’’’’’’Sq(0&

（2）又上述方法得Sq(0&状态01{q】q3}{q3q2}{q0q,q2q3}{q3q2}{q3q2}{q0q]q3}{q0q1q2q3}{q1q2q3}{q0q1q2q3}{q0q1q3}{q1q2q3}{q0q1q2q3}{q1q2q3}{q3q2}{q0q1q2q3}q°={q1q3}，q『{q3q2}，q2={q0^iq2q3}，q3={q0^iq3}，q4={qiq2q3}因为各状态均含有终止状态，所以q0,q1，q2，q3,q4均为终止状态’’’’S注：本题没有必要按照NFA到DFA转化的方法来做，而且从s-NFA到NFA转化时状态没有必要改变，可以完全采用s-NFA中的状态如⑴S状态0iq0（开始状态）{qoq.%qJ{气&,%,q3}q.{qoq.%qJ{q.q。qJq2{qoq.%q』{q.q2qJq3（终止状态）{qo,&,气,qJ{qo,qi,q。,qJ⑵状态o1qo（开始状态）{q.q2q3}{qoqiq。q』_q{q「"{q.q「-q2{q。qJ1，2{qoq2qJq3（终止状态）,L,3空O,2,3_i^d&$$$$$$$$$$*!-力力力力力$$$$$$$$$$$$$$$“$$$$$$$$$$$$$$$kJ-力力力力力力力$$$$$$$$&个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个16.证明对于V的FAM1=(Q1,E1,81,q01,F1)，FAM1=(Q2,E2,82,q02,F2)，存在FAM，使得L(M)=L(M1)UL(M2)(褚颖娜02282072)证明：不妨设Q1与Q2的交集为空(1)构造M=(Q1UQ2U{q°},；8,q0，F)其中：e=e1ue2f=f1uf26(q0,e)={q0i,q02}对于VqGQ1,aeE18(q,a)=5i(q,a)对于Vq£Q2,a£E2,6(q,a)=62(q,a)(3)证明：1)首先证L(M1)UL(M2)EL(M)设xGL(M1)UL(M2)，从而有xEL(M])或者xEL(M2),当xGL(M1)时61(qo1,x)GF1由M的定义可得：6(q0,x)=6(qo,ex)=6(6(qo,e),x)=6({q01,q02},x)=6(q01,x)U6(q02,x)=61(q01,x)U6(q01,x)EF]U6(q01,x)即xEL(M)同理可证当xEL(M2)时xEL(M)故L(M])UL(M2)EL(M)2)再证明L(M)EL(M])UL(M2)设xEL(M)则6(q0,x)EF由M的定义：6(q0，x)=6(q0,ex)=6(6(q0,e),x)=6({q01,q02}，x)=6(q01,x)U6(q02,x)如果是6(q01,x)因为Q1与Q2的交集为空而且6(q0,x)GFF=F1UF2贝6(q01,x)=61(q01,x)GF1因此x£L(M1)如果是6(q02,x)因为Q1与Q2的交集为空而且6(q0,x)GFF=F1UF2贝6(q02,x)=62(q02,x)GF1因此x£L(M2)因此xEL(M1)UL(M2)L(M)EL(M1)UL(M2)得证因此L(M)=L(M1)UL(M2)“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************(唐明珠02282084)17证明：对于任意的FAM=(Q,£,8,q,F),FAM=(Q,£,8,q,F),11110112222022存在FAM,使得L(M)=L(M1)L(M2).证明：令M=(Q1Q2,Z,8,q01,{f2}),其中6的定义为：1)对VqEQj-ifJ,a£EU{e}8(q,a)=81(q,a)；对VqEQ2-{f2}，a£EU{£}8(q,a)=82(q,a)；8(f1，£)={q02}要证L(M)=L(M)L(^)，只需证明L(M)L(M)cL(M),L(M)L(M)mL(M)1.证明L(M1)L(M2)cL(M)设xeL(M)L(M),从而有工eL(M)并且xeL(M),121122使得x=xxm]在处理气的过程中,经过的状态全部都是q中的状态，所以在定义M时，对VgeQ,aeE,5(q,x)=5(q,a)故8(q,x)=5(q,x)={f}TOC\o"1-5"\h\z01110121M2在处理七的过程中,经过的状态全部都是％中的状态，所以在定义M时，对VqeQ,aeE,8(q,x)=5(q,a)5(q,x)=5(q,x)={f}022012下面证明xeL(M)5(q,x)=5(q,xx)

010112=5(5(q,x),x)=5(5(q,x),x)10112=5(f],x2)=5(f],£x2)=5(5(f],8),x2)=5(q02,x2)=5(q,x)2022={f2}即得证xeL(M)2)再证明L(M)cL(M)L(M)设xeL(M)，艮口5(q01,x)={f}由于M是从q：启动的，由M的定义可知,心要达到状态八，必须先至虬.由于除了对应状态转移函数式5(f1，8)={q02}的移动外，不存在从1出发的任何其他移动，而且该移动是2的必经移动,所以,比存在x的前缀x和后缀x，使得x=xx,并且xTOC\o"1-5"\h\z12121将心从状态q引导到状态/,x将心从状态q引导到状态/0112022即5(q,x)=5(q,xx)010112=5(f1，x2)=5(f1，8x2)=5(q,x)这表明xgL(M)xgL(M)从而x=xxgL(M)L(M)1212故L(M)qL(M)L(M)综上所述，12L(M)=L(M1)L(M2FAM=(QZ8qF)22,2,2,02,2*******************************************************************************(吴丹02282090)18.证明：对于任意的FAM=(Q.Z8q.FAM=(QZ8qF)22,2,2,02,212证明：不妨将这些FA看成DFA212/01、02(q,p)gQ?([q,p],a)=[8(q,a),8(p,a).取M=(Q]xQ/ZfZ2,8,{q0],q」，对于VagZJIZ2，，一/_\1设：xgL(M)则女=x1x2xk其中xz4gQ,k])使得8(Iq,p],xi)=[81(q,xi),8(p,xi)]/.xigL(M.)nL(M)nxgL(M.)p|L(M)从而可得L(M)qL(M「nL(mJ设：xgL(M)nL(M)则女=x1x2......xk其中xiGgI1,k])gZAZ有8](q,xi)且82(p,xi)从而使得81212/01、02(q,p)gQ?([q,p],a)=[8(q,a),8(p,a).xigL(m)nxgL(m)从而可得L(MjnL(M)qL(M)综合(1)(2)可得L(M)=L(M「nL(mJ。又因为faBdfa具有等价性，，所以原命题得证。“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个19、总结本章定义的所有FA,归纳出它们的特点，指出它们之间的差别。（吴玉涵02282091）本章学习了DFA，NFA,e-NFA,2DFA和2NFA所有的FA都是一个五元组M=（Q,N，5,q0,F）最大的区别就是状态转移函数5对于DFA，字母表中的每个字母都有唯一确定的状态转移函数。也就是说V5（q,a）EQXS,qGQ，aEN只有唯一确定的状态。对于NFA，对于字母表中的每个输入字符可以有不同的状态转移，对于8串，是一个到自身的移动。对于sNFA，是指在不接受任何字符的情况下，自动机的状态可以发身转移。对于2DFA，对于字母表中的每个字符，对于每个状态都有唯一的状态转移，即V5（q，a）EQXS，qEQ，aES只有唯一确定的状态。与DFA不同的是，2DFA的读头可以在一次状态转移中不移动，或者回退一个，或者向下读一个。对于2NFA，与2DFA相似，但是并不是对于字母表中的每个输入字符都有转移函数，2NFA与2DFA的区别类似于DFA与NFA的区别。“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************20构造如图3-20所个的DFA对应的右线性文法。（周期律02282067）对图1：构造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}ST0A|1|1CAt0S|1|1CP：Bt010C|1SCT0A|1A对图2：构造文法G=（V，T，P，S），其中V={S，A，B，C}，T={1，0}ST0A|1BAt1S|1|0BP：Bt0C|0|1ACT0A|1A“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************21.构造下图所示DFA对应的左线性文法。（吴贤珺02282047）⑴图形如下所示解：设q0、q1、q2、q3所对应的字符分别为A、B、C、G。由于q2为不可达状态，故先去掉该状态。得到该图所对应的左线性文法为:G-A1|B1|1B-G0|G1|A0|0A—B0⑵图形如下所示:解：图中有多个终结状态，为方便起见，增加一个终结状态（红色表示），设该状态所对应的字符为G。又设q0、q1、q2、q3所对应的字符分别为A、B、C、D。则该图所对应的左线性文法为：G-C0|B0|eD-C0C-B0|A1|1B-C1|D0|D1|A0|0A-B1*******************************************************************************22.根据下列给定文法，构造相应的FA。(敖雪峰02282068)(1)文法G1的产生式集合如下：G1:S-alAaA-alAalcAlBbB—alblclaBIBblCb(2)文法G2的产生式集合如下：G2:S—alAa

A—alAalAcIBbB—alblcIBalBblBc解答：文法G1对应的FA如下所示e“$$$$$$$$$$$$$$$力力力力力力力力$$$$$$$$$$$$$$$$$力、mi，&“$$$$$$$力力力“******************************************************************************23.FAM的移动函数定义如下：(冯蕊02282075)%3)叫}(q0，1)=(q1}(q1,0)={q2}(q1?1)={q3}5(q2,0)={q2}5(q3,1)={q3}其中,q2,q3为终态.M是DFA吗?为什么？不是，因为并不是所有的状态,在接收一个字母表中的字符时会有一个状态与之对应.画出相应的DFA的状态转移图0,1,3⑶给出你所画出的DFA的每个状态q的set(q):set(q)={xlx£N*且5(q0,x)=q}set(q0)={3*}set(q1)={3*1}set(q2)={3*100*}set(q3)={3*111*}set(q)={(3*013*1313*100*(113)13*111*(013))0*1*3*}⑷求正则方法G/吏L（G）=L（M）q0—3q0|1q1qL0q2|1q3q2一010q2q3—mq3*******************************************************************************24,总结规约与派生的对应关系，以及与FA的识别过程的对应关系。（段季芳02282073）答：对于左线性文法来说，句子a1a2....an-1an按派生来看，字符在句子中出现的顺序是相反的，即anan-1...a2a1按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序是一致的，即".••气-1*FA识别时，如果存在状态转移5（A，a）=B，表示A后紧跟一个a时，要规约到B；如果B是终结符号，则A后紧跟一个a时，要规约到该文法的开始符号；如果A是开始状态，则a要规约到B。对于右线性文法来说，句子a1a2....an-1an按派生来看，字符在句子中出现的顺序也就是a1a2..an-1an按规约来看，被规约成语法变量的顺序和他们在句子中出现的顺序是相反的，即anan-1...a2a1FA识别时，如果存在状态转移5（A，a）=B，则表示遇到A则派生成aB；但如果B是终结符号，则将A推导为a。******************************************************************************25证明左线性文法与FA等价。（唐明珠02282084）证明：1）根据左线性G（E）文法构造对应的FAM=（Q,Z,6,q0,F）为了形如A—。的产生式，增加一个开始状态Z，使得q0=Z所以E=F,对于产生式8TAa，则有8(A,a)=B,对于产生式8BTa,且旧是开始状态，则有8(E,a)=B.下面证明G(E)与FA等价,即证明L(G(E))=L(M)不会：)2)根据FAM=(Q,Z,8,q0,F)，构造相应的G(E)为了方便起见，在根据给定的FA构造等价的左线性文法的之前，先对FA做如下的处理：删除FA的陷阱状态。在FA中增加一个识别状态“复制”一条原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态。相应的文法的构造依照如下两条进行：如果8(A,a)=B，则有产生式BTa如果8(A,a)=B,且A是开始状态q0,则有产生式BTa。“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““*******************************************************************************(吴丹02282090)证明定理3-6。(2DFA与FA等价)证明：对于2DFAM是一个五元组M=(Q，Z，8，q，F)其中，Q，Z，q0，F的意义同与DFA。8:QxZtQx{l，R，S}，对于V(q，a)gQx^，如果8(q，a)={p，L}表示在读入a从状态q转移到状态p，并将读头向左移动，指向输入字符的前一个字符。如果8(q，a)={p，R}表示在读入a从状态q转移到状态p，并将读头向右移动，指向输入字符的下一个字符。如果8(q，a)={p，S}表示在读入a从状态q转移到状态p，读头保持在原位置不动。我们构造与之等价的FA“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““““***********************************