自动机理论、语言和计算导论课后习题答案(中文版)

1、SolutionsforSection2.2Exercise2.2.1(a)Statescorrespondtotheeightcombinationsofswitchpositions,andalsomustindicatewhetherthepreviousrollcameoutatD,i.e.,whetherthepreviousinputwasaccepted.Let0representapositiontotheleft(asinthediagram)and1apositiontotheright.Eachstatecanberepresentedbyasequenceofthree

2、0'sor1's,representingthedirectionsofthethreeswitches,inorderfromlefttoright.Wefollowthesethreebitsbyeitheraindicatingitisanacceptingstateorr,indicatingrejection.Ofthe16possiblestates,itturnsoutthatonly13areaccessiblefromtheinitialstate,000r.Hereisthetransitiontable:杠杆可能出现8种情况，影响着最终状态。并且也要说明，

3、前面一个大理石球是否从D滚出，也就是说，前一个输入是否被接受。令0代表向左方的状态(如图表)，1代表向右方。这三个杠杆的每一个状态都可以用三个数(0或1)组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。AB->000r100r011r*000a100r011r*001a101r000a010r110r001a*010a110r001a011r111r010a100r010r111r*100a010r111r101r011r100a*101a011r100a110r000a1

4、01a*110a000a101a111r001a110aExercise2.2.2Thestatementtobeprovedis&hat(q,xy)=&hat(-hat(q,x),y),andweproceedbyinductiononthelengthofy.证明：通过对|y|进行归纳,来证明?(q,xy)=，(g(q,x),y),具体过程如下：Basis:Ify=,ihenthestatementis>hat(q,x)=-ha&-hat(q,x),.ThjsstatementfollowsfromthebasisinthedefinitionofMat.No

5、tethatinapplyingthisdefinition,wemusttreat&hat(q,x)asifitwerejustastate,sayp.Then,thestatementtobeprovedisp=-hat(p,whichiseasytorecognizeasthebasisinthedefinitionof占hat.基础：y=0,则y=£0那么需证g(q,x)=?(q,x),户记p=g(q,x),命题变为p=，(p,£,)由，的定义知这显然成立。Induction:Assumethestatementforstringsshorterthany,

6、andbreaky=za,whereaisthelastsymbolofy.Thestepsconverting&hat(-hat(q,x),y)to&hat(q,xy)aresummarizedinthefollowingtable:归纳：假设命题对于比y短的用成立，且y=za,其中a是y的结尾符号。g(g(q,x),y)到£(q,xy)的变换总结在下表中：Expression表达式Reason原因8(缸q,x),y)Start开始8(8(q,x),za)y=zabyassumption由假设y=za浮(风q,x),z),a)DefinitionofMat,trea

7、ting&hat(q,x)asastateg的定义，把M(q,x)看作是一个状态6声(q,xz),a)Inductivehypothesis归纳假设?(q,xza)DefinitionofWhat笈的定义?(q,xy)y=zaExercise2.2.4(a)TheintuitivemeaningsofstatesA,B,andCarethatthestringseensofarendsin0,1,oratleast2zeros.状态A,B,C分别表示以1,0和00结尾的用的状态。01->ABABCA*CCAExercise2.2.6(a)Thetrickistorealizeth

8、atreadinganotherbiteithermultipliesthenumberseensofarby2(ifitisa0),ormultipliesby2andthenadds1(ifitisa1).Wedon'tneedtoremembertheentirenumberseen-justitsremainderwhendividedby5.Thatis,ifwehaveanynumberoftheform5a+b,wherebistheremainder,between0and4,then2(5a+b)=10a+2b.Since10aissurelydivisibleby5

9、,theremainderof10a+2bisthesameastheremainderof2bwhendividedby5.Sinceb,is0,1,2,3,or4,wecantabulatetheanswerseasily.Thesameideaholdsifwewanttoconsiderwhathappensto5a+bifwemultiplyby2andadd1.对于一个二进制整数，如果读入一个比特0,其值等于原数乘以2;否则等于原数乘以2再加以1。而任意一个数均可写成形如5a+b,其中a任意,0<=b<=4,那么输入0,原数变为2(5a+b)=10a+2b,由于10a是

10、5的倍数，因此10a+2b除以5的余数与2b相同。输入1,则得2(5a+b)+1类似。因此对于所有的数只要记住它被5除的余数就可以。由于b是0,1,2,3或者4,我们可以容易得到该DPA的转移表，具体如下：Thetablebelowshowsthisautomaton.Stateqimeansthattheinputseensofarhasremainderiwhendividedby5.其中状态qi代表输入用被5除的余数i的状态->*q0q0q1q1q2q3q2q0q3q4q1q3q2q4Thereisasmallmatter,however,thatthisautomatonacce

11、ptsstringswithleading0's.Sincetheproblemcallsforacceptingonlythosestringsthatbeginwith1,weneedanadditionalstates,thestartstate,andanadditional''deadstate''d.If,instates,weseea1first,weactlikeq0;i.e.,wegotostateq1.However,ifthefirstinputis0,weshouldneveraccept,sowegotostated,which

12、weneverleave.Thecompleteautomatonis:但是上述自动机仍接受以0开头的字符串。因为题目要求只接受以1开头的用，可增加一个初始状态s和“死亡状态"do在状态初始状态s,若看到1,则转到状态q1；若看到0,则直接转到状态d,识别终止。所求自动机如下：011->sd1q1*q0q0q1q1q2q3q2q4q0q3q1q2q4q3q4dddExercise2.2.9Part(a)isaneasyinductiononthelengthofw,startingatlength1.Basis:|w|=1.Then&hatgw)=-hat(qf,w),

13、becausewisasinglesymbol,and占hatagreeswith6onsinglesymbols.Induction:Letw=za,sotheinductivehypothesisappliestoz.Thenhat(qo,w)=&hat(qo,za)=-hat(qo,z),a)=-ha(qf,z),a)bytheinductivehypothesis=(-hat(qf,za)=-hat(qf,w).证明：a)通过对w长度的归纳证明基础：若|w|=1,则w是一个符号，此时需证M(qo,w)=9(qf,w),而对于单个符号扩展转移函数M与转移函数6的作用是一样的，得证

14、。归纳：令w=za,假设又t于z命题8(qo,z)=?(qf,z)成立。那么?(qo,w)=?(qo,za)=6充(qo,z),a)=程6(qf,z),a)由归纳假设=?(qf,za)=?(qf,w).Forpart(b),weknowthat&hat(qo,x)=qf.Sincex£,weknowbypart(a)that&hat(qf,x)=qf.Itisthenasimpleinductiononktoshowthat-hat(qo,xk)=qf.6Basis:Fork=1thestatementisgiven.Induction:Assumethestatem

15、entfork1;i.e.,-hatp,xSUP>k-1)=qf.UsingExercise2.2.2,-hat(q0,xk)=-hat(-hat(q0,xk-1),x)=-hat(qf,x)bytheinductivehypothesis=cfby(a).b)x是属于L(A)的非空用，也即用x被接收，因此g(qo,x)=qf,则由a)知g(qf,x)=?(qo,x)=qfo现在通过对k的归纳来证明?(qo,xk)=qf。基础：k=1时，需证&(qo,x)=qf,由已知可得。归纳：假设又t于k-1命题成立，也就是说，名(qo,xk-1)=qf。由练习2.2.2,B?(qo,xk)

16、=g(M(qo,xk-1),x)=g(qf,x)由归纳假设=qf由(a)。Exercise2.2.10Theautomatontellswhetherthenumberof1'sseeniseven(stateA)orodd(stateB),acceptinginthelattercase.Itisaneasyinductionon|w|toshowthatdh(A,w)=Aifandonlyifwhasanevennumberof1's.Basis:|w|=0.Thenw,theemptystringsurelyhasanevennumberof1's,namelyz

17、ero1's,and?(A,w)=A.Induction:Assumethestatementforstringsshorterthanw.Thenw=za,whereaiseither0or1.Case 1: a=0.Ifwhasanevennumberof1's,sodoesz.Bytheinductivehypothesis,?(A,z)=A.ThetransitionsoftheDFAtellus?(A,w)=A.Ifwhasanoddnumberof1's,thensodoesz.Bytheinductivehypothesis,-hat(A,z)=B,and

18、thetransitionsoftheDFAtellus-hat(A,w)=B.Thus,inthiscase,-hat(A,w)寸Aifandonlyifwhasanevennumberof1's.Case 2: a=1.Ifwhasanevennumberof1's,thenzhasanoddnumberof1's.Bytheinductivehypothesis,-hat(A,z)=B.ThetransitionsoftheDFAtellus-hat(A,w)=6A.Ifwhasanoddnumberof1's,thenzhasanevennumberof

19、1's.Bytheinductivehypothesis,-hat(A,z)=A,andthetransitionsoftheDFAtellus-hat(A,w)=B.6Thus,inthiscaseaswell,-hat(A,w)=Aifandonlyifwhasanevennumberof1's.这个自动机表示，状态A表示偶数个1,状态B表示奇数个1,不管用有偶数个还是奇数个1,都会被接受。当且仅当用w中有偶数个1时(A,w)=A.0用归纳法证明如下基础：|w|=0。空用当然有偶数个1,即0个1,且£(A,w)=A.归纳：假设对于比w短的用命题成立。令w=za,其

20、中a为0或1情形1:a=0.如果w有偶数个1,则z有偶数个1。由归纳假设，?(A,z)=A由转移表的DFA知M(A,w)=A.如果w有奇数个1,则z有奇数个1.由归纳假设,?(A,z)=B,由转移表的DFA知，(A,w)=B.因此这种情况下6?(A,w)=A当且仅当w有偶数个1。情形2:a=1.如果w有偶数个1,则z有奇数个1。由归纳假设，?(A,z)=B.由转移表的DFA知M(A,w)=A.如果w有奇数个1,则z有偶数个1。由归纳假设，g(A,z)=A,由转移表的DFA知歹(A,w)=B.因此这种情况下M(A,w)=A当且仅当w有偶数个1.综合上述情形，命题得证。SolutionsforSe

21、ction2.3Exercise2.3.1HerearethesetsofNFAstatesrepresentedbyeachoftheDFAstatesAthroughH:A=p;B=p,q;C=p,r;D=p,q,r;E=p,q,s;F=p,q,r,s;G=p,r,s;H=p,s.下表就是利用子集构造法将NFA转化成的DFA。其中构造的子集有：A=p;B=p,q;C=p,r;D=p,q,r;E=p,q,s;F=p,q,r,s;G=p,r,s;H=p,s.Exercise2.3.4(a)Theideaistouseastateqi,fori=0,1,.,9torepresenttheidea

22、thatwehaveseenaninputiandguessedthatthisistherepeateddigitattheend.Wealsohavestateqs,theinitialstate,andqf,thefinalstate.Westayinstateqsallthetime;itrepresentsnoguesshavingbeenmade.Thetransitiontable:记状态qi为已经看到i并猜测i就是结尾将要重复的数字，i=0,1,.,9。初始状态为qs,终止X犬态为qf。我们可以一直停留在状态qs,表示尚未猜测。转移表如下：01.9->qsqs,q0qs,

23、q1.qs,q9q0qf)q0.q0q1q1|qf).q1.1.q9q9q9.qf)*qf).)SolutionsforSection2.4Exercise2.4.1(a)We'lluseq0asthestartstate.q1,q2,andq3willrecognizeabc;q4,q5,andq6willrecognizeabd,andq7throughq10willrecognizeaacd.Thetransitiontableis:记q0为初始状态。q1,q2和q3识别abc;q4,q5和q6识别abd,q7到q10识另Iaacd.转移表如下：abcd->q0q0,q1,

24、q4,q7q0q0q0q1)q2)q2)q3_*q3)_q4k)q5)_q5)q6*q6)q7q8)q8)q9)q9q101*q10口Exercise2.4.2(a)Thesubsetconstructiongivesusthefollowingstates,eachrepresentingthesubsetoftheNFAstatesindicated:A=q0;B=q0,q1,q4,q7;C=q0,q1,q4,q7,q8;D=q0,q2,q5;E=q0,q9;F=q0,q3;G=q0,q6;H=q0,q10.NotethatF,GandHcanbecombinedintooneaccept

25、ingstate,orwecanusethesethreestatetosignaltherecognitionofabc,abd,andaacd,respectively.由子集构造法可得以下DFA的状态，其中每一个状态都是NFA状态的子集：A=q0;B=q0,q1,q4,q7;C=q0,q1,q4,q7,q8;D=q0,q2,q5;E=q0,q9;F=q0,q3;G=q0,q6;H=q0,q10.注意到F,G和H可以整合到一个接受状态中，或者我们可以用这三个状态能分别标记已识别abc,abd和aacda->ABBC1CCDBEB*FB*GB*HBbcdAAADAADEAAFGAAHA

26、AAAAAAAASolutionsforSection2.5Exercise2.5.1Forpart(a):theclosureofpisjustp;forqitisp,q,andforritisp,q,r.(a):根据状态的e闭包的的性质。求得，p的e闭包：p;q的e闭包：p,q;r的e闭包：p,q,r。For(b),beginbynoticingthataalwaysleavesthestateunchanged.Thus,wecanthinkoftheeffectofstringsofb'sandc'sonly.Tobegin,noticethattheonlywayst

27、ogetfromptorforthefirsttime,usingonlyb,c,and-transitionsarebb,bc,andc.Aftergettingtor,wecanreturntorreadingeitherborc.Thus,everystringoflength3orless,consistingofb'sandc'sonly,isaccepted,withtheexceptionofthestringb.However,wehavetoallowa'saswell.Whenwetrytoinserta'sinthesestrings,ye

28、tkeepingthelengthto3orless,wefindthateverystringofa'sb's,andc'swithatmostoneaisaccepted.Also,thestringsconsistingofonecandupto2a'sareaccepted;otherstringsarerejected.b）由于输入a状态总是保持不变，因此只需考虑输入b和c的情况。可以看出，从状态p第一次到r且只经过b,c和e转移的路径为bb,be和c;到r之后，读入b仍可回到r,读入c回到p,则可通过继续读入用bb,bc和c回到r。&clos

29、ure因此，每一个由b和c组成的长度小于等于3的用可以被接受，除了用b不能接受。向这些用中插入a,并保持长度小于等于3,就会得到所有由a,b,c组成的，至多含有一个a的可被接受的用。由一个c和两个a组成的任意用也是可以被接受的。其它的用均被拒绝。TherearethreeDFAstatesaccessiblefromtheinitialstate,whichistheorp.LetA=p,B=p,q,andC=p,q,r.Thenthetransitiontableis:由初始状态，即p的e闭包或者p,有3个状态可以达到。令A=p,B=p,q,C=p,q,r。转移表如下：->AABB*C

30、CCCSolutionsforSection3.1Exercise3.1.1(a)Thesimplestapproachistoconsiderthosestringsinwhichthefirstaprecedesthefirstbseparatelyfromthosewheretheoppositeoccurs.Theexpression:c*a(a+c)*b(a+b+c)*+c*b(b+c)*a(a+b+c)*首先考虑第一个a在第一个b的前面，然后再考虑相反的情况。表达式为：c*a(a+c)*b(a+b+c)*+c*b(b+c)*a(a+b+c)*Exercise3.1.2(a)(Rev

31、ised9/5/05)Thetrickistostartbywritinganexpressionforthesetofstringsthathavenotwoadjacent1's.Hereisonesuchexpression10+0)*(+1)Toseewhythisexpressionworks,thefirstpartconsistsofallstringsinwhichevery1isfollowedbya0.Tothat,wehaveonlytoaddthepossibilitythatthereisa1attheend,whichwillnotbefollowedbya

32、0.Thatisthejobof(e+1).首先写出没有两个1相邻的用的集合，如下：(10+0)*(+1)。表达式的第一部分表示每个1之后都紧跟一个0的这样的用组成。为了表示结尾可能是1的情况，则可在串尾处加上(£+1)Now,wecanrethinkthequestionasaskingforstringsthathaveaprefixwithnoadjacent1'sfollowedbyasuffixwithnoadjacent0's.Theformeristheexpressionwedeveloped,andthelatteristhesameexpressi

33、on,with0and1interchanged.Thus,asolutiontothisproblemis(10+0)*(吐1)(01+1)*(廿0).Notethatthe&+1terminthemiddleisactuallyunnecessary,asa1matchingthatfactorcanbeobtainedfromthe(01+1)*factorinstead.题目要求的用可由两部分组成，也就是，前缀没有相邻的1,后缀没有相邻的00前半部分也就是已经给出的(10+0)*(+1),根据对称性后半部分可将上式的1和0交换得到。所求即为(10+0)*(+1)(01+1)*(

34、+0)。注意中间的e+1项没有作用，因为1可以由后面的(01+1)*项得到。因此最后得到的正则表达式为(10+0)*(01+1)*(吐0)Exercise3.1.4(a)Thisexpressionisanotherwaytowrite''noadjacent1's.''Youshouldcompareitwiththedifferent-lookingexpressionwedevelopedinthesolutiontoExercise3.1.2(a).Theargumentforwhyitworksissimilar.(00*1)*saysever

35、y1isprecededbyatleastone0.0*attheendallows0'safterthefinal1,and(1)atthebeginningallowsaninitial1,whichmustbeeithertheonlysymbolofthestringorfollowedbya0.你可以与练习3.1.2(a)中我们给出的不同样子的表达式作比较。为什么起作用的原因是类似的。这个表达式是“没有相邻的1”的另一种描述方式。(00*1)*表示每个1的前面都至少有一个0做前缀。最后的0*允许在最后一个1后面有00开头的(£1)允许初始为1,要么用就只有这一个符号

36、，要么后面跟着的就是00Exercise3.1.5Thelanguageoftheregularexpression&.Notethat8*denotesthelanguageofstringconsistingofanynumberofemptystrings,concatenated,butthatisjustthesetcontainingtheemptystring.正则表达式&e装示由任意多个空审组成的用，也是只包含空用的集合。SolutionsforSection3.2Exercise3.2.1Part(a):ThefollowingareallR0expressi

37、ons;welistonlythesubscripts.R11=1;e+R12=0;R13=phi;R21=1;R22=£R20;=R31=phi;R32=1;R33=0.+a)下面就是所有R0的表达式；我们只写出下标：R11=&侏R12=0;R13=中(phi);R21=1;R22=£R20;=R31=(phi);R32=1;R33=0.+Part(b):HereallexpressionnamesareR;weagainlistonlythesubscripts.R11=1*;R12=1*0;R13=phi;R21=11*;R22=1#0;R23=0;R31=p

38、hi;R32=1;R33=4b)下面就是所有R的表达式；我们只写出下标：R11=1*;R12=1*0;R13=phi;R21=11*;R22=11*0;R23=0;R31=phi;R32=1;R33=0.十Part(e):Hereisthetransitiondiagram移图:Ifweeliminatestateq2weget:如果消除状态q2,有：Applyingtheformulainthetext,theexpressionforthewaystogetfromq1toq3is:1+01+00(0+10)*11*00(0+10)*由课本中的公式，q1至Iq3的正则表达式：1+01+00

39、(0+10)*11*00(0+10)*Exercise3.2.4(a)利用定理3。7每个用正则表达式来定义的语言也可用穷自动机来定义Exercise3.2.6(a)(Revised修改1/16/02)LL*orL+.Exercise3.2.6(b)ThesetofsuffixesofstringsinL.(以)L中用(作为)后缀/下标的集合。Exercise3.2.8LetR(k)ijmbethenumberofpathsfromstateitostatejoflengthmthatgothroughnostatenumberedhigherthank.Wecancomputethesenum

40、bers,forallstatesiandj,andformnogreaterthann,byinductiononk.令R(k)ijm为从状态i到状态j,长度为m,且没有经过编号大于k的路径的个数。对于所有状态I和j,以及m(m<n),通过对k归纳来计算这个个数。Basis:R0ij1isthenumberofarcs(ormoreprecisely,arclabels)fromstateitostatej.R0ii0=1,andallotherRijm'sare0.基础：k=0,R0ij1是由状态i到状态j的箭弧(更准确的说，是箭弧标号)的个数R0ii0=1,其他的R0ijm

41、's都为0。Induction:R(k)ijmisthesumofR(k-1)ijmandthesumoveralllists(p1,p2,.,pr)ofpositiveintegersthatsumtom,ofRk-1)ikp1*R(k-1)kkp2*R(k-1)kkp3*.*R(k-1)kkp(r-1)R(k-1)kjpr.Notermustbeatleast2.归纳：R(k)ijm是R(k-1)ijm的和，R(k-1)ikp1*R(k-1)kkp2*R(k-1)kkp3*.*R(k-1)kkp(r-1)*R(k-1)kjpr。(p1,p2,.,pr)是所有和为m的正整数序列，r大

42、于等于2。TheansweristhesumofRk)1jn,wherekisthenumberofstates,1isthestartstate,andjisanyacceptingstate.答案就是R(k)1jn的总和，其中k是状态个数，1为开始状态，j是任意接受状态SolutionsforSection3.4Exercise3.4.1(a)ReplaceRbyaandSbyb.Thentheleftandrightsidesbecomeaunionb=buniona.Thatis,a,b=b,a.Sinceorderisirrelevantinsets,bothlanguagesare

43、thesame:thelanguageconsistingofthestringsaandb.将R替换为a,S替换为b。等式变为a+b=b+a.也就是a,b=b,a.因为集合中元素的顺序是无关紧要的，所以，等式两边是一样的：由用a和b构成的语言。Exercise3.4.1(f)ReplaceRbya.Therightsidebecomesa*,thatis,allstringsofa's,includingtheemptystring.Theleftsideis(a*)*,thatis,allstringsconsistingoftheconcatenationofstringsofa

44、's.Butthatisjustthesetofstringsofa's,andisthereforeequaltotherightside.将R替换为a。右边变为a*,代表a组成的所有用，包含空用。左边是(a*)*,代表由a组成的用构成的申，也就是由a构成的申。当然相等。Exercise3.4.2(a)Notthesame.ReplaceRbyaandSbyb.Theleftsidebecomesallstringsofa'sandb's(mixed),whiletherightsideconsistsonlyofstringsofa's(alone)

45、andstringsofb's(alone).Astringlikeabisinthelanguageoftheleftsidebutnottheright.不等。将R替换为a,S替换为b。左边表示所有由a和b(可混合)构成的用。而右边表示只有a构成的用和只有b构成的用。像ab这样的用就只属于左边的语言，而不属于右边。Exercise3.4.2(c)Alsonotthesame.ReplaceRbyaandSbyb.Therightsideconsistsofallstringscomposedofzeroormoreoccurrencesofstringsoftheforma.ab,

46、thatis,oneormorea'sendedbyoneb.However,everystringinthelanguageoftheleftsidehastoendinab.Thus,forinstance,&isinthelanguageontheright,butnotontheleft.不等。举反例，将R替换为a,S替换为b。右边表示由0个或多个形如a.ab组成的申，也就是，一个或多个a后面紧跟一个结尾的bo但是，左边的用必须以ab结尾。因此，e属于右边的语言，但不属于左边。SolutionsforSection4.1Exercise4.1.1(c)Letnbethe

47、pumping-lemmaconstant(notethisnisunrelatedtothenthatisalocalvariableinthedefinitionofthelanguageL).Pickw=0n10n.Thenwhenwewritew=xyz,weknowthat|xy|<=n,andthereforeyconsistsofonly0's.Thus,xz,whichmustbeinLifLisregular,consistsoffewerthann0's,followedbya1andexactlyn0's.ThatstringisnotinL

48、,sowecontradicttheassumptionthatLisregular.令n为泵引理常数(这个n与语言L的定义中的局部变量n无关)。设w=0n10n。把w打断为w=xyz,满足|xy|<=n,则y只由0构成。若L是正则的，那么xz一定在L中。但xz由少于n个0,后面跟着一个1和恰好n个0构成。这个用不在L中。所以L不是正则语言。Exercise4.1.2(a)Letnbethepumping-lemmaconstantandpickw=012,thatis,n20's.Whenwewritew=xyz,weknowthatyconsistsofbetween1and

49、n0's.Thus,xyyzhaslengthbetweenn+1andn2+n.Sincethenextperfectsquareafternis(n+1)2=n2+2n+1,weknowthatthelengthofxyyzliesstrictlybetweentheconsecutiveperfectsquaresnand(n+1).Thus,thelengthofxyyzcannotbeaperfectsquare.Butifthelanguagewereregular,thenxyyzwouldbeinthelanguage,whichcontradictstheassump

50、tionthatthelanguageofstringsof0'swhoselengthisaperfectsquareisaregularlanguage.令n为泵引理常数，设w=0n2,也就是n2个0。将w打断为w=xyz。y是由大于1小于n个0组成的。因此xyyz的长度介于n2+1和n2+n之间。n2的下一个完全平方数是(n+1)2=n2+2n+1。因为xyyz的长度介于n2和(n+1)2之问。所以xyyz的长度不是完全平方数。若语言是3则的，那么xyyz也应该是正则的。xyyz的长度应该是完全平方数。矛盾。所以语言不是正则的。Exercise4.1.4(a)Wecannotpi

51、ckwfromtheemptylanguage.我4无法从空集中找至Uw,因为y非空。Exercise4.1.4(b)Iftheadversarypicksn=3,thenwecannotpickawoflengthatleastn.如果对手选择n=3,那么我们无法找到长度至少为n的w。Exercise4.1.4(c)Theadversarycanpickann>0,sowehavetopickanonemptyw.Sincewmustconsistofpairs00and11,theadversarycanpickytobeoneofthosepairs.Thenwhateveriwe

52、pick,xyizwillconsistofpairs00and11,andsobelongsinthelanguage.对手选择n>0,我们就要选择一个非空的w。因为w必须由成对的00和11组成，对手可以选择这些对中的一个。那么不管我们选择什么样的i,xyiz都由00和11组成，所以属于语言。SolutionsforSection4.2Exercise4.2.1(a)aabbaa.Exercise4.2.1(c)Thelanguageofregularexpressiora(ab)*ba.正则表达式语言a(ab)*baExercise4.2.1(e)Eachbmustcomefrome

53、ither1or2.However,ifthefirstbcomesfrom2andthesecondcomesfrom1,thentheywillbothneedtheabetweenthemaspartofh(2)andh(1),respectively.Thus,theinversehomomorphismconsistsofthestrings110,102,022.每个b必须来自1或2。如果第一个b来自2和第二个来自1,那么将需要两个a在他们之间分别作为h(2)和h(1)的一部分，这种情况不行。因此，逆同态组成的字符串110,102,022。Exercise4.2.2Startwit

54、haDFAAforL.ConstructanewDFAB,thatisexactlythesameasA,exceptthatstateqisanacceptingstateofBifandonlyif6(q,a)sanacceptingstateofA.ThenBacceptsinputstringwifandonlyifAacceptswa;thatis,L(B)=L/a.首先从L的一个DFAA出发。我们构造一个DFAB,满足当且仅当6(q,亚A的一个接受状态时，状态q才是B的一个接受状态。因此，当且仅当A接受wa时，B接受输入用w;即L(B)=L/a。(DFA的语言是正则的)Exerci

55、se4.2.5(b)WeshalluseDafor''thederivativewithrespecttoa."ThekeyobservationisthatifepsilonisnotinL(R),thenthederivativeofRSwillalwaysremoveanafromtheportionofastringthatcomesfromR.However,ifepsilonisinL(R),thenthestringmighthavenothingfromRandwillremoveafromthebeginningofastringinL(S)(whi

56、chisalsoastringinL(RS).Thus,therulewewantis:我们用Da表示导数a'。关键是，如果£不在L(R)中，则RS的导数总是能从R的字符串中去掉a。如果£在L(R)中，则R可能是空，这时从L(S)的字符串头去掉a.因此，总的规则就是：IfepsilonisnotinL(R),thenDa(RS)=(Da(R)S.Otherwise,Da(RS)=Da(R)S+Da(S).如果£不在L(R),则Da(RS)=(Da(R)S.否则，Da(RS)=Da(R)S+Da(S).Exercise4.2.5(e)L中没有以0开始的字符串

57、.Lmayhavenostringthatbeginswith0.Exercise4.2.5Thisconditionsaysthatwhenever0wisinL,thenwisinL,andvice-versa.Thus,LmustbeoftheformL(0*)MforsomelanguageM(notnecessarilyaregularlanguage)thathasnostringbeginningwith0.这个条件说明如果0w在L中，则w就在L中，反之亦然。因此，L必须是这样的形式L(0*)M,其中语言M没有包含以0开始的用。Inproof,noticefirstthatDo(L(0*)M=Do(L(0*)MunionDo(M)=L(0*)M.Therearetworeasonsforthelaststep.First,observethatDappliedtothelanguageofallstringsof0'sgivesallstringsof