2. 计算机
  3. 已知一不确定的有限自动机(NFA)如图2-8所示，采用子集法将其确定化为DFA的过程如表2-1所示。 　状态集T1中不包括编号为(23)的状态；状态集T2中的成员有(24)：状态集T3等于(25)；该自动机所识别的语言可以用正规式(26)表示。

已知一不确定的有限自动机(NFA)如图2-8所示，采用子集法将其确定化为DFA的过程如表2-1所示。 　状态集T1中不包括编号为(23)的状态；状态集T2中的成员有(24)：状态集T3等于(25)；该自动机所识别的语言可以用正规式(26)表示。

admin2019-03-11  57
问题 已知一不确定的有限自动机(NFA)如图2-8所示，采用子集法将其确定化为DFA的过程如表2-1所示。

　状态集T1中不包括编号为(23)的状态；状态集T2中的成员有(24)：状态集T3等于(25)；该自动机所识别的语言可以用正规式(26)表示。
选项 A、(0｜1)*
B、(0*｜1*)*001
C、(0*｜1*)*0(0｜1)*
D、(0*｜1*)0(0｜1)*
答案D
解析 将NFA转换为DFA一般用于集法。下面用子集法来进行转换。
    首先，K0=ε_closure(0)=(S，1，2，3)，这是初始集，也就是初始状态。这里值得注意的一点是图中ε表示空，从S到1是ε箭头线，所以如果能到达S，也就能到达1。所以如果图2-2的初态实际上包含S，1，2，3四个。因此在表2-1中，第一行第一列是{S1，2，3}。
   接下来对初态集{S，1，2，3)输入0，即K1=ε_closure[move(K0，0)]={1，3，4，5，Z}，所以第一行I0列对应的数据为{1，3，4，5，Z}。
   接着K2=ε_closure(move(K0，1))={2，3}，所以第一行I1列对应的数据为{2，3}。
   依次类推：
   令K3=ε_closure(move(K1，0))={1，3，4，5，6，Z}，
   令K4=ε_closure(move(K1，1))={}。
   最终求得T1={1，3，4，5，6，Z}，T2{4，5，Z}，T3={}，据此可以得出答案。
转载请注明原文地址:https://kaotiyun.com/show/SMRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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