A.(－d|d)d*E(－d|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*.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[-｜E(-｜d)d*]}

D．(-d｜d)dd*E(-d｜d)d*｜(-d｜d)dd*.d*[ε｜E(-dd*｜dd*)]

Answer 1

正确答案：A
解析：DFA能识别的字符串是指一条从初态节点到终态节点的路径上所有弧上的标记符所连接龙的字符串。我们依次检查备选项看哪些字符串不能被DFA接受。首先看“3875”，这个字符扫中的元素全是数字，从初态0出发输入一个数字进入状态1：在状态1输入一个数字还是回到状态1，无法前进。所以①不能被DFA接受。接着看“1.2E+5”，这个不用判断都可以知道不行，因为“+”在DFA中不能识别。再看“-123.”，该串能从初态0到达终态5，所以能被只别。最后一个备选项中首字符“.”在初始状态无法被识别，所以不能被DFA识别。然后我们把DFA转化为正规式。首先可以排除B和D，很显然(-d｜d)dd*所表达的串比所描述的多一个d。再看Cs选项中(-｜d)dd*E(-｜d)d*表示不经过状态5的路径，而后面的-d｜d)dd*.d*{ε｜E[-｜E(-｜d)d*]})是指经过状态5的路径，所以C也被排除。这样答案只能选择A了。