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

=1226志文工作室1SolutionsforSection2.2Exercise2.2.1(a)Statescorrespondtotheeightcombinationsofswitchpositions,andalsomustindicatewhetherthepreviousrollcameoutatD,i.e.,whetherthepreviousinputwasaccepted.Let0representapositiontotheleft(asinthediagram)and1apositiontotheright.Eachstatecanberepresentedbyasequenceofthree0'sor1's,representingthedirectionsofthethreeswitches,inorderfromlefttoright.Wefollowthesethreebitsbyeitheraindicatingitisanacceptingstateorr,indicatingrejection.Ofthe16possiblestates,itturnsoutthatonly13areaccessiblefromtheinitialstate,000r.Hereisthetransitiontable:杠杆可能出现8种情况，影响着最终状态。并且也要说明，前面一个大理石球是否从D滚出，也就是说，前一个输入是否被接受。令0代表向左方的状态（如图表），1代表向右方。这三个杠杆的每一个状态都可以用三个数（0或1）组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。AB-000r100r011r*000a100r011r*001a101r000a010r110r001a*010a110r001a011r111r010a100r010r111r*100a010r111r101r011r100a*101a011r100a110r000a101a*110a000a101a111r001a110aExercise2.2.2Thestatementtobeprovedisδ-hat(q,xy)=δ-hat(δ-hat(q,x),y),andweproceedbyinductiononthelengthofy.=1226志文工作室2证明：通过对|y|进行归纳，来证明ˆ(q,xy)=ˆ(ˆ(q,x),y)，具体过程如下：Basis:Ify=ε,thenthestatementisδ-hat(q,x)=δ-hat(δ-hat(q,x),ε).Thisstatementfollowsfromthebasisinthedefinitionofδ-hat.Notethatinapplyingthisdefinition,wemusttreatδ-hat(q,x)asifitwerejustastate,sayp.Then,thestatementtobeprovedisp=δ-hat(p,ε),whichiseasytorecognizeasthebasisinthedefinitionofδ-hat.基础:y=0，则y=ε。那么需证ˆ(q,x)=ˆ(ˆ(q,x),ε)，记p=ˆ(q,x),命题变为p=ˆ(p,ε),由ˆ的定义知这显然成立。Induction:Assumethestatementforstringsshorterthany,andbreaky=za,whereaisthelastsymbolofy.Thestepsconvertingδ-hat(δ-hat(q,x),y)toδ-hat(q,xy)aresummarizedinthefollowingtable:归纳:假设命题对于比y短的串成立,且y=za,其中a是y的结尾符号。ˆ(ˆ(q,x),y)到ˆ(q,xy)的变换总结在下表中:Expression表达式Reason原因ˆ(ˆ(q,x),y)Start开始ˆ(ˆ(q,x),za)y=zabyassumption由假设y=zaδ(ˆ(ˆ(q,x),z),a)Definitionofδ-hat,treatingδ-hat(q,x)asastateˆ的定义,把ˆ(q,x)看作是一个状态δ(ˆ(q,xz),a)Inductivehypothesis归纳假设ˆ(q,xza)Definitionofδ-hatˆ的定义ˆ(q,xy)y=zaExercise2.2.4(a)TheintuitivemeaningsofstatesA,B,andCarethatthestringseensofarendsin0,1,oratleast2zeros.状态A,B，C分别表示以１,０和00结尾的串的状态。=1226志文工作室301-ABABCA*CCAExercise2.2.6(a)Thetrickistorealizethatreadinganotherbiteithermultipliesthenumberseensofarby2(ifitisa0),ormultipliesby2andthenadds1(ifitisa1).Wedon'tneedtoremembertheentirenumberseen---justitsremainderwhendividedby5.Thatis,ifwehaveanynumberoftheform5a+b,wherebistheremainder,between0and4,then2(5a+b)=10a+2b.Since10aissurelydivisibleby5,theremainderof10a+2bisthesameastheremainderof2bwhendividedby5.Sinceb,is0,1,2,3,or4,wecantabulatetheanswerseasily.Thesameideaholdsifwewanttoconsiderwhathappensto5a+bifwemultiplyby2andadd1.对于一个二进制整数，如果读入一个比特０，其值等于原数乘以２；否则等于原数乘以２再加以1。而任意一个数均可写成形如5a+b，其中a任意，0=b=4，那么输入0，原数变为2(5a+b)=10a+2b，由于10a是5的倍数,，因此10a+2b除以５的余数与2b相同。输入1，则得2(5a+b)+1类似。因此对于所有的数只要记住它被５除的余数就可以。由于b是0,1,2,3或者4,我们可以容易得到该DPA的转移表，具体如下：Thetablebelowshowsthisautomaton.Stateqimeansthattheinputseensofarhasremainderiwhendividedby5.其中状态qi代表输入串被５除的余数i的状态。01-*q0q0q1q1q2q3q2q4q0q3q1q2q4q3q4Thereisasmallmatter,however,thatthisautomatonacceptsstringswithleading0's.Sincetheproblemcallsforacceptingonlythosestringsthatbeginwith1,weneedanadditionalstates,thestartstate,andanadditional``deadstate''d.If,instates,weseea1first,weactlikeq0;i.e.,wegotostateq1.However,ifthefirstinputis0,weshouldneveraccept,sowegotostated,whichweneverleave.Thecompleteautomatonis:=1226志文工作室4但是上述自动机仍接受以０开头的字符串。因为题目要求只接受以１开头的串，可增加一个初始状态s和“死亡状态”d。在状态初始状态s,若看到１，则转到状态q1；若看到０,则直接转到状态d，识别终止。所求自动机如下:01-sdq1*q0q0q1q1q2q3q2q4q0q3q1q2q4q3q4dddExercise2.2.9Part(a)isaneasyinductiononthelengthofw,startingatlength1.Basis:|w|=1.Thenδ-hat(q0,w)=δ-hat(qf,w),becausewisasinglesymbol,andδ-hatagreeswithδonsinglesymbols.Induction:Letw=za,sotheinductivehypothesisappliestoz.Thenδ-hat(q0,w)=δ-hat(q0,za)=δ(δ-hat(q0,z),a)=δ(δ-hat(qf,z),a)[bytheinductivehypothesis]=δ-hat(qf,za)=δ-hat(qf,w).证明：a)通过对w长度的归纳证明。基础:若|w|=1，则w是一个符号，此时需证ˆ(q0,w)=ˆ(qf,w),而对于单个符号扩展转移函数ˆ与转移函数δ的作用是一样的，得证。归纳:令w=za,假设对于z命题ˆ(q0,z)=ˆ(qf,z)成立。那么ˆ(q0,w)=ˆ(q0,za)=δ(ˆ(q0,z),a)=δ(ˆ(qf,z),a)[由归纳假设]=ˆ(qf,za)=ˆ(qf,w).Forpart(b),weknowthatδ-hat(q0,x)=qf.Sincexε,weknowbypart(a)thatδ-hat(qf,x)=qf.Itisthenasimpleinductiononktoshowthatδ-hat(q0,xk)=qf.Basis:Fork=1thestatementisgiven.=1226志文工作室5Induction:Assumethestatementfork-1;i.e.,δ-hat(q0,xSUPk-1)=qf.UsingExercise2.2.2,δ-hat(q0,xk)=δ-hat(δ-hat(q0,xk-1),x)=δ-hat(qf,x)[bytheinductivehypothesis]=qf[by(a)].b)x是属于L(A)的非空串，也即串x被接收，因此ˆ(q0,x)=qf，则由a)知ˆ(qf,x)=ˆ(q0,x)=qf。现在通过对k的归纳来证明ˆ(q0,xk)=qf。基础:k=1时，需证ˆ(q0,x)=qf，由已知可得。归纳：假设对于k-1命题成立，也就是说，ˆ(q0,xk-1)=qf。由练习2.2.2,ˆ(q0,xk)=ˆ(ˆ(q0,xk-1),x)=ˆ(qf,x)[由归纳假设]=qf[由(a)]。Exercise2.2.10Theautomatontellswhetherthenumberof1'sseeniseven(stateA)orodd(stateB),acceptinginthelattercase.Itisaneasyinductionon|w|toshowthatdh(A,w)=Aifandonlyifwhasanevennumberof1's.Basis:|w|=0.Thenw,theemptystringsurely