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

单选题 A.①、②、③ B.①、②、④
C.②、③、④ D.①、②、③、④
【正确答案】 B
【答案解析】
单选题 A.(-d|d)d*E(-d|d)d*|(-did)*.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
【答案解析】本题考查有限自动机。
有限状态自动机识别字符串的过程是:初始时,处于起始状态(题图中节点0表示初始状态);依次读取一个字符,并进行相应的状态转移,直到输入串结束或找不到相应的状态转移为止。字符串被DFA接受是指从初态开始到终态(图中双圈节点表示终态),所输入的字符串能够按顺序执行下去。
根据本题给出的状态机,我们来分别看一下①~④中每个字符串的识别过程:
·3857:状态转换过程为[*],到最后一个字符“7”识别完以后,状态机仍处于中间状态1,而非终态,因此不会接受此字符串。
·1.2E+5:状态转换过程为[*],识别完字符“E”到状态2以后,后面一个字符“+”已无路径可走,因此无法接受此字符串。
·-123.:状态转换过程为[*],字符串识别完成并且到达终态,因此可以接受。
·.576E10:该字符串的第一个字符“.”都无法中初态0找到下一步的路径,因此不会被接受。
分析题中给出的有穷状态机,可知该自动机识别以下形式的数值:带小数部分的十进制表示形式和以尾数、指数表示的数值形式,其中由初态0到终态5所识别的是带小数点的以十进制数值表示形式的字符串,小数点后可以没有数值,也可以有若干数字,而小数点之前的整数部分可以不带符号,也可以带负号,其正规式为(-d|d)d*.d*。当数值的表示含有指数部分时(由
初态0到终态6),指数部分是不带符号或带负号的整数形式,该部分的正规式为E(-d|d)d*。