某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|1|2|…|9，则以下字符串中，不能被该DFA接受的是 (3) ，与该DFA等价的正规式是 (4) 。 (其中，ε表示空字符)
①3857 ②1.2E+5 ③-123 ④.576E10
①3857 ②1.2E+5 ③-123 ④.576E10
【正确答案】
B
【答案解析】
【正确答案】
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了。
题目第一问是判断备选答案中有哪些字符串不能被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了。