资源描述：
《自动机理论、语言和计算导论课后习题答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、http://www.zhiwenweb.cn/article.asp?id=1226SolutionsforSection2.2Exercise2.2.1(a)Statescorrespondtotheeightcombinationsofswitchpositions,andalsomustindicatewhetherthepreviousrollcameoutatD,i.e.,whetherthepreviousinputwasaccepted.Let0representapositiontotheleft(asinthediagram)and1apos
2、itiontotheright.Eachstatecanberepresentedbyasequenceofthree0'sor1's,representingthedirectionsofthethreeswitches,inorderfromlefttoright.Wefollowthesethreebitsbyeitheraindicatingitisanacceptingstateorr,indicatingrejection.Ofthe16possiblestates,itturnsoutthatonly13areaccessiblefromthein
3、itialstate,000r.Hereisthetransitiontable:杠杆可能出现8种情况，影响着最终状态。并且也要说明，前面一个大理石球是否从D滚出，也就是说，前一个输入是否被接受。令0代表向左方的状态（如图表），1代表向右方。这三个杠杆的每一个状态都可以用三个数（0或1）组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。AB->000r100r011r*000a100r011r*001a101r000a010r110r001a*010
4、a110r001a011r111r010a100r010r111r*100a010r111r101r011r100a*101a011r100a110r000a101a*110a000a101a111r001a110aExercise2.2.2Thestatementtobeprovedisδ-hat(q,xy)=δ-hat(δ-hat(q,x),y),andweproceedbyinductiononthelengthofy.志文工作室1http://www.zhiwenweb.cn/article.asp?id=1226证明：通过对
5、y
6、进行归纳，来证明δˆ(
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.Then,thestatementtobeprovedisp=δ-hat(p,ε),whichiseasytorecogn
8、izeasthebasisinthedefinitionofδ-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:
9、归纳:假设命题对于比y短的串成立,且y=za,其中a是y的结尾符号。δˆ(δˆ(q,x),y)到δˆ(q,xy)的变换总结在下表中:Expression表达式Reason原因δˆ(δˆ(q,x),y)Start开始δˆ(δˆ(q,x),za)y=zabyassumption由假设y=zaDefinitionofδ-hat,treatingδ-hat(q,x)asastateδ(δˆ(δˆ(q,x),z),a)δˆ的定义,把δˆ(q,x)看作是一个状态δ(δˆ(q,xz),a)Inductivehypothesis归纳假设δˆ(q,xza)Definitionof
10、δ-hatδˆ的定义δˆ
