计算理论课后习题答案

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 习题,1,给定文法,G=(S,B,C,D,E,0,1,P,S)，,其中,P：,SABC，AB0AD，AB1AE，AB，D00D，D11D，E00E，E11E，C，DCB0C，ECB1C，0BB0，1BB1,试写出句子01100110的派生过程。,解,：,S,AB,C,0A,D,C,0,A,B,0C,0,1A,E,0,C01A,0,E,C,01A,0,B,1C,01,A,B,0,1C01,1A,E,0,1C011A,0,E,1,C,011A0,1,E,C,011A0,1,B,1C,011A,0,B,1,1C011,A,B,0,11C,011,0A,D,0,11C0110A,0,D,1,1C0110A0,1,D,1,C,0110A01,1,D,C,0110A01,1,B,0C,0110A0,1,B,1,0C,0110A,0,B,1,10C0110,A,B,0,110C01100110C01100110,2,设计下列各文法,G，,使得它们分别是：,（1）,G,是个上下文无关文法，且,L(G)=a,i,b,j,c,k,i,j,k1。,（2）,G,是个正规文法，且,L(G)=a,i,b,j,c,k,i,j,k1。,（3）,G,是个上下文无关文法，且,L(G)=ww,R,w0,1,+,。,其中,w,R,是,w,的逆转，例,如,w=001,则,w,R,=100.,解,：设计一个文法,G,要验证,：,凡是符合要求的句子,G,都能产生出来；,G,产生出来的所有句子都是符合要求的。,(1),G=(S,A,B,C,a,b,c,P,S),P:S,ABC,A,aA|a,BbB|b,CcC|c,(2),G=(S,A,B,C,a,b,c,P,S),P:S,a,A,A,aA|bB,BbB|cC,CcC|,(3),G=(S,0,1,P,S),P:S0S0|1S1|00|11,第二章 习题,1,设计一个有限自动机(,FA)M，,使得,T(M),中的每个句,子,w,同时满足下面三个条件：,1),wa,b,*,；,2),|w|,是3的整数倍；,3),w,以,a,开头，以,b,结尾。,解：,q,0,q,1,q,3,q,2,q,4,a,a,b,a,b,a,b,b,2,设计二个,FA M,1,和,M,2,，,分别满足,T(M,1,)=0,2i,i,是自然数,T(M,2,)=0,2i+1,i=0,1,2,3,4,解：,M,1,：,q,0,q,1,q,3,0,0,0,q,1,q,0,0,0,q,0,q,1,0,0,M,2,：,3.,给定,NFA M,1,=(p,q,r,s,0,1,p,s)，,如下表所示。,构造一个,DFA M,2,，,使得,T(M,1,)=T(M,2,)。,解,：令,M,2,=(K,q,0,F),其中,K,2,K,，K,中的元素是由,K,的子集,q,1,q,2,q,i,构成，但是要把子集,q,1,q,2,q,i,作为的一个状态看待，,因此把此子集写成,q,1,q,2,q,i,。,q,0,=,q,0,F,=q,1,q,2,q,i,|q,1,q,2,q,i,K,且,q,1,q,2,q,i,F,：KK，,对,q,1,q,2,q,i,K,a，,有,(,q,1,q,2,q,i,a)=p,1,p,2,p,j,当且仅当,(q,1,q,2,q,i,a)=p,1,p,2,p,j,0 1,p p,q p,q r r,r s ,s s s,q,0,=,p,K,和,F,以后确定。,：,0 1,p p,q p,q r r,r s ,s s s,p,0,1,p,q,p,p,q,p,q,r,p,r,p,r,p,q,s,p,p,q,r,p,q,r,s,p,r,p,q,s,p,q,r,s,p,r,s,p,r,s,p,q,s,p,s,p,s,p,q,s,p,s,p,q,r,s,p,q,r,s,p,r,s,K,=,p,p,q,p,r,p,s,p,q,r,p,q,s,p,r,s,p,q,r,s,F,=,p,s,p,q,s,p,r,s,p,q,r,s,p,p,q,p,r,p,q,r,p,q,s,p,r,s,p,s,p,q,r,s,0,1,0,0,0,0,0,0,1,0,1,1,1,1,1,1,4.,将下面的,-NFA M,等价变换成,NFA M。,a,b,c,d,e,f,1,0,1,0,：对任何,qK,任何,a,(q,a)=(q,a)。,解,：,M=(K,q,0,F)，q,0,是,M,的开始状态，其中,公式(1),：对于,qK,(q,)=-CLOSURE(q),公式(2),：对于,qK,w,*,a,(q,wa)=-CLOSURE(q,w),a),因为,f,CLOSURE(a)=a,b,所以,F=F=f,：,qK,任何,a,a,b,c,d,e,f,1,0,1,0,(q,a)=(q,a)。,在计算 (,q,a),时，要将,a,理解成,a,路径,！,例如,(a,0)=(a,0)=c,e,d,b。,:,0,1,abcdef,c,e,d,b,d,b,d,b,f,f,d,b,f,d,b,f,f,d,b,5,化简正规表达式,a(+aa),*,(+a)b+b+(ab,*,+b),*。,解,：,上式,a(aa)*(+a)b+b,其中(,aa)*(+a),代表集合：,aa,aaaa,aaaaaa,a,=,aa,aaaa,aaaaaa,a,aaa,aaaaa,=,a,aa,aaa,aaaa,aaaaa,aaaaaa,=,a*,于是上式,aa*b+b=a,+,b+b=,(a,+,+)b=a*b,6,构造一个,FA M，,使得,T(M),的正规表达式为,01+(0+1),*,1),*,。,解,：,1,.分解表达式，找出基本单元：0,1,01,1。设计接收,这些基本单元的自动机如下：,q,1,q,2,0,q,3,q,4,1,q,7,q,8,1,q,5,q,6,0,q,9,q,10,1,2.组装：（按照优先权从高到低）01+(0+1),*,1),*,q,7,q,8,1,q,5,q,6,0,q,9,q,17,1,q,0,q,15,q,10,q,16,q,12,q,2,q,1,0,q,3,q,4,1,q,14,q,13,q,11,7,给定,FA M,如下图所示，求它所接收的语言,T(M),的正,规表达式。,解,：,q,2,q,1,0,0,1,1,8.,将下面有限自动机简化(要求有简化过程)。,解,：,一.定义,K,上等价关系,给定,DFA,M=(K,q,0,F)，,p,qK,p,q,对,x,*,有,(p,x)F,(q,x)F,如果,p,q,也称,p,与,q,是不可区分的。,二.,商集,K/,三,的逆关系,p,q,x(x,*,(p,x)F,(q,x)F),x(x,*,(p,x)F(q,x),F)(p,x),F(q,x)F),x(x,*,，,使得,(p,x),与,(q,x),恰有一个在,F,中),如果,p,q,称,p,与,q,是可区分的,。判断,p,q,是比较容易的。,a,b,c,f,e,d,0,0,1,0,0,0,1,0,1,1,1,1,4判断可区分状态对的算法,引理2-1,设,M=(K,q,0,F),是,DFA，,则状态对(,p,q),是可区分,的(即,p,q)，,当且仅当在下面算法中(,p,q),格写上。,begin,1for pF,qK-F,do,给(,p,q),格写；,2,for FF,或(,K-F)(K-F),中每个状态对(,p,q)(pq)，do,3if,a，,使得格(,(p,a),(q,a),内已经写上，,then,begin,4,给(,p,q),格写；,5 如果刚刚写上的格内有先前写入的状态对，此状态对,的格同时也写入。反复执行5,直到写入的格内没,有先前写入的状态对为止；,end,else/*,格(,(p,a),(q,a),内无 */,6,for,每个,a,do,7,把(,p,q),写入格(,(p,a),(q,a),内，除非,(p,a)=(q,a)。,end,执行此算法的结果用一个表表示，实际上，执行此算,法的过程就是向这个表内写入,“,”,的过程。,a b c d e,b,c,d,e,f,(,b,d),a,b,c,f,e,d,0,0,1,0,0,0,1,0,1,1,1,1,(a,b):,ab,0 1,be,?,(a,c):,ac,0 1,ba,(a,d):,ad,0 1,bf,bd,0 1,cd,0 1,ef,0 1,bc,0 1,(,b,c):,(,b,d):,(,c,d):,(,e,f):,ea,ef,fe,af,dd,fe,得：,b,d,e,f,a,a,c,c,于是,K/,a,b,d,c,e,f，,五构造简化的有限自动机,定理2-5.1,给定,DFA M(K,q,0,F)，,可根据引理2-1中,的算法构造出除去不可达状态的具有更少状态的,DFA M，,使得,T(M)=T(M)。,证明：,先对,M,用引理2-1中的算法求出,K/,。,再构造,M：,M=(K,q,0,F)，,其中,K=q|qK/,且在,M,中,q,是从,q,0,可达的状态,F=q|qF,：,对任何,qK，,任何,a,(q,a)=(q,a),K/,a,b,d,c,e,f=a,b,c,e，(b=b,d,e=e,f,),K=a,b,c,e F=e,M=(K,a,F),=(a,b,c,e,0,1,a,e),(q,a)=(q,a),a,b,c,f,e,d,0,0,1,0,0,0,1,0,1,1,1,1,:,0 1,abce,b,c,b,e,a,a,e,e,a,b,0,c,1,e,0,1,0,1,0,1,9,给定,DFA M,如图所示。求一个左线性文法,G，,使得,L(G)=T(M)。,解,：有两种方法。,方法1,1.,先将,M,逆转成,M：,B,A,C,1,0,1,0,0,1,B,A,C,1,0,1,0,0,1,S,2.,根据,M,构造右线性文法,G：,S,A|C|,A0B,B0A|0C|1C|0,C1A|1B|1,3.,将,G,逆转成左线性文法,G:,SA|C|,AB0,BA0|C0|C1|0,CA1|B1|1,P=q,ap|(q,a)=pq,a|(q,a)F。,方法2,1.,先根据,M,构造右线性文法,G：,A0B|1C|1 (,其中,A,是开始变元),B0A|1C|0|1,C0B|1B,2.,再将,G,直接变成左线性文法,G:,根据定理：,(1),S,当且仅当,S,P；,(2)A,i,当且仅当,S,A,i,P；,(3)A,i,A,j,当且仅当,A,j,A,i,P；,(4)S,A,j,当且仅当,A,j,P。,(1),由,A1,得:,A1,(2),由,A0B,得:,B0,由,A1C,得:,C1,(3),由,B0A,得:,A B0,由,B1C,得:,CB1,由,C0B,得:,BC0,由,C1B,得:,BC1,(4),由,B0,得:,AB0,由,B1,得:,AB1,B,A,C,1,0,1,0,0,1,方法2,1.,先根据,M,构造右线性文法,G：,A0B|1C|1|,(,其中,A,是开始变元),B0A|1C|0|1,C0B|1B,因开始变元,A,出现在产生式右侧，故引入新的开始变元,S，,SA(,其中,S,是开始变元),A0B|1C|1|,B0A|1C|0|1,C0B|1B,B,A,C,1,0,1,0,0,1,2.,再将,G,直接变成左线性文法,G:,根据定理：,(1),S,当且仅当,S,P；,(2)A,i,当且仅当,S,A,i,P；,(3)A,i,A,j,当且仅当,A,j,A,i,P；,(4)S,A,j,当且仅当,A,j,P。,(2),SA,得:,A,(3),由,A0B,得:,BA0,由,A1C,得:,CA1,由,B0A,得:,A B0,由,B1C,得:,CB1,由,C0B,得:,BC0,由,C1B,得:,BC1,(4),由,A1,得:,SA1,由,A,得:,SA,由,B0,得:,SB0,由,B1,得:,SB1,整理得左线性文法,G:,SA1|