2. 计算机
  3. 已知一个NFA　M图如下所示，采用子集构造法将其确定化为DFA的过程如下表所示。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 表中的状态集合T

已知一个NFA　M图如下所示，采用子集构造法将其确定化为DFA的过程如下表所示。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 表中的状态集合T

admin2009-02-15  66
问题 已知一个NFA　M图如下所示，采用子集构造法将其确定化为DFA的过程如下表所示。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

表中的状态集合T是(27)。
选项 A、{1，2}
B、{3，4，5}
C、{4，5}
D、{6}
答案B
解析 对于每个NFA M都存在一个DFA M’，使得L(M’)=L(M)
   有一个方法称为子集构造法，能将一个非确定的有限自动机转换成一个等价的确定的有限自动机。
   具体说来，对于给定的一个NFA M，设想有一个DFA M’，它的初态是NFA M的初态q0以及从q0出发沿空弧所能到达的那些状态，表示成I=ε_closure(q0)在M中一个状态和一个输入符号可能转换到多个状态，若在NFA M中有I×a∈∑→JQ(表示成J=move(I，a)，J是NFA M中所有那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体)，那么，在DFA M’中设状态Ia=ε_closure(J)，ε_closure(J)称为ε_闭包，其计算方法下面予以介绍。这实际上是用DFA M’模拟NFA M的动作，重复这个模拟过程，直到M’中不再增加新的状态。这个过程将逐步构造出DFA M’的状态转移矩阵表，图中NFA M的DFA M’的状态转移矩阵如表所示。
   ε_closure(T)称为子集T的ε_闭包，计算方法如下：
   (1)ε_closure(T)=T;
   (2)q∈ε_closure(T)，若δ(q, ε)=q’，则把q’加到ε_closure(T)中，直到ε_closure(T)不再增大为止。也就是说，ε_closure(T)不仅含有T，而且含有从T出发沿空弧所能到达的所有状态，直观理解是去掉NFA M的空弧。
   表中I是M状态集的一个子集，首先求DFA M’的初态，表[0，0]=ε_closure(0)={0,1,2}，然后求I0和I1。表[0,1]=ε_closurre(move({0,1,2},0))=ε_closure({1})={1,2}表[0,2]=ε-closure(move({0,1,2},1))=ε_closure({3})={3,4,5}
   如果I0和I1不出现在表的第1列I中，则把它们填入第1列I下面的空行位置上。之后，对I的新行上的子集重复求I0和I1，直至所有第2列和第3列的子集全都在第1列中出现为止。这个过程必定在有限步内终止，因为M的状态子集的个数是有限的。
   T=ε_closure(move({1,2},1))=ε_closure(move({3})={3,4,5}。
转载请注明原文地址:https://www.kaotiyun.com/show/DJxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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