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

admin2017-08-31  35

问题 某确定性有限自动机(DFA)的状态转换图如图2.1所示,令d=0|1|2|…|9,则以下字符串中,能被该DFA接受的是(    )。

选项 A、80008
B、1—2.E+5
C、一968.12
D、12.576E10

答案C

解析 本题考查确定性有限自动机,是常考的知识点。
一个DFA可以表示成一个状态图(或称状态转换图)。假定DFAM含有m个状态,n个输入字符,那么这个状态图含有m个结点,每个结点最多有n个弧射出,整个图含有唯一一个初态结点和若干个终态结点,初态结点冠以双箭头“=>”或标以“-”,终态结点用双圈表示或标以“+”,若f(ki,a)=kj,则从状态结点ki到状态结点kj画标记为a的弧;被DFA所接受是指从初态开始来终态,所输入的字符串能够按顺序的执行下去,若到某个状态不能往下走得到下一个字符,则认为不可接受。本题的状态图的状态间的字符有一、d、E、.,下面来逐个分析4个选项:
    A选项不能被接受。由于80008都是数字,所以从初态0出发不经过状态4,而是直接到状态1,因为0和1之间产生字符为d,又在状态1处有d*,所以表面可以接受“dddd”形式的字符串;但是,状态l之后的产生字符是E和.,不再是数字d,若输入全数字则到不了终态6。所以输入3857是不能接受的。
    B选项不能被接受。从初态0→4→1→2,就不能再往下走了,因为状态2后的产生字符是“一、d”,不是“+”,也无法到达终态6。
    C选项能被接受。从初态0→4→1→5→6,由于状态1和6处的可以反复多个字符,所以本选项正确。
    D选项不能被接受。从初态0→1→5→6,虽然从初态到终态,但无法接受字符E了,所以错误。
转载请注明原文地址:https://jikaoti.com/ti/OEf7FFFM
0

相关试题推荐
最新回复(0)