2. 计算机
  3. 某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是(3)，与该DFA等价的正规式是(4)。 (其中，ε表示空字符) ①3857 ②1.2E+5 ③-123 ④.

某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是(3)，与该DFA等价的正规式是(4)。 (其中，ε表示空字符) ①3857 ②1.2E+5 ③-123 ④.

admin2019-03-04  42
问题 某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是(3)，与该DFA等价的正规式是(4)。 (其中，ε表示空字符)
①3857   
②1.2E+5   
③-123   
④.576E10

选项 A、(-d|d)d*E(-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(-|d)d*)
D、(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(ε|E(-dd*|dd*))
答案A
解析 题目第一问是判断备选答案中有哪些字符串不能被DFA接受。现在逐个对其进行判别，这样有利于对DFA功能的理解和后面的解题。
   首先看3857，这个字符串中的元素全部是数字，从DFA的初态0输入一个数字，进行到状态1，在状态1输入数字还是回到状态1，如果还想往后走，必须要输入字符“．”或是字符“E”，但3857中不存在这样的字符，所以无法到达终态，因此①不能被 DFA接受。
   接着看1.2E+5，这个不用判断就知道不行，因为“+”在此DFA中无法识别。
   再看-123.，此串能从始点顺利到达终点(状态0→状态4→状态1→状态1→状态 1→状态5)，所以此串可以被DFA接受。
   最后看.576E10，第一个字符“．”在初始状态无法被识别，所以此串也不能被DFA识别。
   接下来是把DFA转化为正规式，我们用排除法来解这个题，首先可以排除的是B和D，很明显(-d|d)dd*所表达的串会比DFA所描述的串多一个d。
   再看C选项(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(ε|E(-|d)d*)。其中的(-|d)dd*E(-|d)d*表示的路径是不经过状态5的路径。后面的(-d|d)dd*.d*(ε|E(-|d)d*)是指经过状态5的路径。这里的(-d|d)dd*，也是多出了一个d，所以C也可以排除，答案就只能是A了。
转载请注明原文地址:https://www.kaotiyun.com/show/JtTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

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