某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|19,则以下字符串中,不能被该DFA

Question

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

①3857

②1.2E+5

③-123．

④.576E10

A．①、②、③

B．①、②、④

C．②、③、④

D．①、②、③、④

Answer 1

正确答案：B
解析：有限自动机也称为有穷状态自动机，是一种数学机器模型，基本形式有非确定有限自动机(NFA)和确定的有限自动机(DFA)，并且每一个NFA都有与其等价的DFA。有穷状态自动机的物理模型如下图所示。

  一个DFA可以用状态转换图直观的方式。状态转换图是一种有向图。DFA中的每个状态对应转换图中的一个节点，从外部引入弧的节点表示开始节点，双圈节点表示终态；DFA中的每个状态转换对应图中的一条有向弧，若转换关系为/(A，a)=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
  有穷状态自动机识别字符串的过程为：初始时，机器处于起始状态(题图中节点0表示初始状态)。读取一个输入符号，并进行相应的状态转移，直到输入串结束或找不到
相应的状态转移时为止。
  根据题目终给定的自动机，识别3857、1.2E+5、-123.、.576E10的过程分别如下。
 
  分析题中给定的有穷状态自动机，可知该自动机识别以下形式的数值：带小数部分的十进制表示形式和以尾数、指数表示的数值形式。其中，从初态0到达终态5所识别的是带小数点的以十进制数值表示形式的字符串，小数点后可以没有数字，也可以有若干个数字，而小数点之前的整数部分可以不带符号，也可以带负号，其正规式为“(-d|d) d*.d，”。当数值的表示含有指数部分时，指数部分是不带符号(表示正数)或带负号的整数形式，因此该部分的正规式为“E(-d|d)d*”。