2. 计算机
  3. 图2-3所示为一确定有限自动机的状态转换图，图中的(15)是可以合并的状态。

图2-3所示为一确定有限自动机的状态转换图，图中的(15)是可以合并的状态。

admin2015-06-03  32
问题 图2-3所示为一确定有限自动机的状态转换图，图中的(15)是可以合并的状态。
选项 A、0和1
B、2和3
C、1和2
D、0和3
答案B
解析 在状态转换图中，每一个结点代表一个状态，其中双圈是终结状态。该题实际上是一个简化确定有限自动机(DFA)的过程，一个确定有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。
    先介绍两个概念：最小状态DFA和等价状态。
    最小状态DFA必须满足以下两个条件。
    (1)没有多余状态(死状态)：多余状态是指从该自动机的开始状态出发，任何输入串都不能到达的那个状态。
    (2)没有两个状态是互相等价(不可区别)。
    两个状态s和t如果同时满足下列两个条件，我们就称s和t是等价的：
    (1)一致性：同是终态或同是非终态。
    (2)蔓延性：从s出发读入某个a和从t出发读入某个a到达的状态等价。
    本题的简化过程如下：
    首先，将图中状态分为终态和非终态两个子集即({0，1}，{2，3})，再进行子集划分。观察第一个子集{0，1}，输入b后，状态O转换为状态1，而状态1转换为状态2。因此{1}和{2}中的状态是可区别的。
    由于状态2，3输入字符a得到相同的结果3，输入字符b得到相同结果2，所以子集{2，3}是不可区别的。从而得到新的划分：({0}，{1}，{2，3})，因此，本题的正确答案为B。
转载请注明原文地址:https://kaotiyun.com/show/XCRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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