您现在的位置：希赛网>云阅读>软件设计师考试试题分类精解（第3版）>例题1第2章：程序语言作者：希赛教育软考学院来源：希赛网2014年02月07日例题12.2试题精解例题1（2005年5月试题28-29）某一确定性有限自动机（DFA）的状态转换如图2-1所示，令d=0|1|2|…|9,则以下字符串中，不能被该DFA接受的是（28）,与该DFA等价的正则式是（29）.（其中，e表示空字符）①3857②1.2E+5③-123④576E10图2-1状态转换图（28）A.①，②，③B.①，②，④C.②，③，④D.①，②，③，④（29）A.（-d|d）d*E（-d|d）d*|（-d|d）d*.d*（e|E（-d|d）d*）B.（-d|d）dd*（。|e）d*|（e|E（-d|d）d*）C.（-|d）dd*E（-|d）d*|（-d|d）dd*.d*（e|E（-|d）d*）D.（-d|d）dd*E（-d|d）d*|（-d|d|）dd*.d*（e|E（-dd*|dd*））试题分析题目第一问是判断备选答案中有哪些字符串不能被DFA接受。我们现在逐个对其进行判别，这样有利于对DFA功能的理解和后面的解题。首先看"3857",这个字符串中的元素全部是数字，在DFA的初态0输入一个数字，进入状态1;在状态1输入数字，还是回到状态1.如果还想往后走，必须要输入字符"."或是字符"E",但3857中不存在这样的字符，因而无法到达终态，所以①不能被DFA接受。接着看"1.2E+5",这个不用判断就知道不行，因为"+"在此DFA中无法识别。再看"-123.",此串能从始点顺利到达终点，所以可以被DFA接受。最后我们看".576E10",第一个字符"."在初始状态无法被识别，所以此串不能被DFA识别。接下来是把DFA转化为正则式。我们用排除法来解答，首先可以排除B和D,很明显（-d|d）dd*所表达的串会比DFA所描述的串多一个d.再看C选项（-|d）dd*E（-|d）d*|（-d|d）dd*.d*（e|E（-|d）d*）。其中（-|d）dd*E（-|d）d*表示的路径是不经过节点5的路径。后面的（-d|d）dd*.d*（e|E（-|d）d*）是指经过节点5的路径。这里的（-d|d）dd*也是多出一个d,所以C也可以排除，答案就只能是A了。试题答案BA版权方授权希赛网发布，侵权必究上一节本书简介下一节第2章：程序语言作者：希赛教育软考学院来源：希赛网2014年02月07日例题2上一节本书简介下一节第2章：程序语言作者：希赛教育软考学院来源：希赛网2014年02月07日例题3例题2（2005年5月试题30）对于以下编号为①，②，③的正则式，正确的说法是_______.①（aa*|ab）*b②（a|b）*b③（（a|b）*|aa）*b（30）A.正则式①，②等价B.正则式①，③等价C.正则式②，③等价D.正则式①，②，③互不等价试题分析由正则式①产生的字...
