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

Question

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*))

Answer 1

正确答案：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了。