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

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

admin2017-08-31  38
问题 某确定性有限自动机(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://kaotiyun.com/show/hNRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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