2. 计算机
  3. 对于下图的DFAM进行化简，与其等价的最少状态的DFAM’是(27)。

对于下图的DFAM进行化简，与其等价的最少状态的DFAM’是(27)。

admin2009-02-15  82
问题 对于下图的DFAM进行化简，与其等价的最少状态的DFAM’是(27)。
选项 A、
B、
C、
D、
答案D
解析 所谓一个DFA M＝(∑，Q，q0，F，δ)的化简是指寻找一个状态数比较少的DFA M’，使L(M)=L(M’)，而且可以证明存在一个最少状态的DFAM’，使L(M’)＝L(M)。
   下面介绍最少状态的DFA和等价状态，最少状态DFA必须满足以下两个条件。
   (1)没有多余状态(死状态)：多余状态是指从该自动机的开始状态出发，任何输入串都不能到达的那些状态。
   (2)没有两个状态是互相等价(不可区别)的。
   设p，q∈Q。若对任何w∈∑*,δ(p,w)∈F当且仅当δ(q，w)∈F，则称状态p和q是等价的。如果p和q不等价，则称p，q是可区别的。
   DFA M的最小化过程是把M的状态集Q分割成一些互不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的。然后在每个子集中任取一个状态做“代表”，而删去子集中其余状态，并把指向其余状态集的箭弧都改作指向这个做“代表”的状态集中。这样得到的状态转换图所对应的DFA M’就是接受L(M)的具有最少状态的DFA。
   两个状态s和t如果同时满足下列两个条件，就称s和t是等价的。
   (1)一致性：同是终态或同是非终态。
   (2)蔓延性：a∈∑，  δ(s,a)=q，δ(t,a)=q’，q，q’等价。
   本题的简化过程如下：首先，将图中状态分为终态和非终态两个子集即({0,2,4}、{1，3})，再进行子集划分，观察第1个子集{0，2，4}，输入。后，状态0转换为状态2，状态2转换为状态2，状态4转换为状态4，输入1后，{0，2，4}中的状态转换到{1，3}。因此子集{0，2，4}不可分割。观察第2个子集{1，3}，输入0后，状态1、3转换到状态3；输入1后，状态1、 3转换到状态4。因此子集{1，3}也是不可分割的。
   重复子集划分步骤，发现状态集无法划分。在子集{0，2，4}中选择0状态作为代表，在子集{1，3}中选择1状态作为代表，画出最少状态的DFA是被选答案中的D。
转载请注明原文地址:https://www.kaotiyun.com/show/VRxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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