对于下图的DFAM进行化简,与其等价的最少状态的DFAM'是(27)。A.B.C.D.

Question

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

A．

B．

C．

D．

Answer 1

正确答案：D
解析：所谓一个DFAM＝(∑，Q，q0，F，δ)的化简是指寻找一个状态数比较少的DFAM'，使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是可区别的。DFAM的最小化过程是把M的状态集Q分割成一些互不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的。然后在每个子集中任取一个状态做“代表”，而删去子集中其余状态，并把指向其余状态集的箭弧都改作指向这个做“代表”的状态集中。这样得到的状态转换图所对应的DFAM'就是接受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。