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

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

admin2015-06-03  87
问题 某确定性有限自动机(DFA)的状态转换图如图2-1所示，令d=0｜1｜2｜…｜9，则以下字符串中，能被该DFA接受的是(8)。
选项 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”形式的字符串；但是，状态1之后的产生字符是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/RCRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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