2. 计算机
  3. 某一确定性有限自动机(DFA)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)

某一确定性有限自动机(DFA)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)

admin2019-03-11  35
问题 某一确定性有限自动机(DFA)的状态转换图如图2-2所示，令d=0｜1｜2｜…19，则以下字符串中，不能被该DFA接受的是(9)，与该DFA等价的正规式是(10)。(其中，ε表示空字符。)

选项 A、(-d｜d)d*E(-d｜d)d*｜(-d｜d)d*.d*[ε｜E(-d｜d)d*]
B、(-d｜d)dd*(.｜ε)d*[ε｜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(-dd*｜dd*)]
答案A
解析 DFA能识别的字符串是指一条从初态节点到终态节点的路径上所有弧上的标记符所连接龙的字符串。我们依次检查备选项看哪些字符串不能被DFA接受。首先看“3875”，这个字符扫中的元素全是数字，从初态0出发输入一个数字进入状态1：在状态1输入一个数字还是回到状态1，无法前进。所以①不能被DFA接受。接着看“1.2E+5”，这个不用判断都可以知道不行，因为“+”在DFA中不能识别。再看“-123.”，该串能从初态0到达终态5，所以能被只别。最后一个备选项中首字符“.”在初始状态无法被识别，所以不能被DFA识别。然后我们把DFA转化为正规式。首先可以排除B和D，很显然(-d｜d)dd*所表达的串比所描述的多一个d。再看Cs选项中(-｜d)dd*E(-｜d)d*表示不经过状态5的路径，而后面的　-d｜d)dd*.d*{ε｜E[-｜E(-｜d)d*]})是指经过状态5的路径，所以C也被排除。这样答案只能选择A了。
转载请注明原文地址:https://jikaoti.com/ti/t2f7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)