资源描述：
《自动机理论语言和计算导论课后习题答案(中文版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SolutionsforSection2.2Exercise2.2.1(a)Statescorrespondtotheeightcombinationsofswitchpositions,andalsomustindicatewhetherthepreviousrollcameoutatD,i.e.,whetherthepreviousinputwasaccepted.Let0representapositiontotheleft(asinthediagram)and1apositiontother
2、ight.Eachstatecanberepresentedbyasequenceofthree0'sor1's,representingthedirectionsofthethreeswitches,inorderfromlefttoright.Wefollowthesethreebitsbyeitheraindicatingitisanacceptingstateorr,indicatingrejection.Ofthe16possiblestates,itturnsoutthatonly13a
3、reaccessiblefromtheinitialstate,000r.Hereisthetransitiontable:杠杆可能出现8种情况，影响着最终状态。并且也要说明，前面一个大理石球是否从D滚出，也就是说，前一个输入是否被接受。令0代表向左方的状态（如图表），1代表向右方。这三个杠杆的每一个状态都可以用三个数（0或1）组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。AB->0
4、00r100r011r*000a100r011r*001a101r000a010r110r001a*010a110r001a011r111r010a100r010r111r*100a010r111r101r011r100a*101a011r100a110r000a101a*110a000a101a111r001a110aExercise2.2.2Thestatementtobeprovedisδ-hat(q,xy)=δ-hat(δ-hat(q,x),y),andweproceedbyinductio
5、nonthelengthofy.证明：通过对
6、y
7、进行归纳，来证明(q,xy)=((q,x),y)，具体过程如下：Basis:Ify=ε,thenthestatementisδ-hat(q,x)=δ-hat(δ-hat(q,x),ε).Thisstatementfollowsfromthebasisinthedefinitionofδ-hat.Notethatinapplyingthisdefinition,wemusttreatδ-hat(q,x)asifitwerejustastate,sayp
8、.Then,thestatementtobeprovedisp=δ-hat(p,ε),whichiseasytorecognizeasthebasisinthedefinitionofδ-hat.基础:=0，则y=ε。那么需证(q,x)=((q,x),ε)，记p=(q,x),命题变为p=(p,ε),由的定义知这显然成立。Induction:Assumethestatementforstringsshorterthany,andbreaky=za,whereaisthelastsymbolofy.Th
9、estepsconvertingδ-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
10、δ-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结尾的串的状态。0
