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

已知一不确定的有限自动机(NFA)如图6-6所示，采用子集法将其确定化为DFA的过程如表6-1所示。 状态集T1中不包括编号为(58)的状态；状态集T2中的成员有(59)；状态集乃等于(60)；该自动机所识别的语言可以用正则式(61)表示。

admin2019-03-04  61
问题 已知一不确定的有限自动机(NFA)如图6-6所示，采用子集法将其确定化为DFA的过程如表6-1所示。
   状态集T1中不包括编号为(58)的状态；状态集T2中的成员有(59)；状态集乃等于(60)；该自动机所识别的语言可以用正则式(61)表示。

选项 A、(0，1)*
B、(0*|1*)*001
C、(0*|1*)*0(0|1)*
D、(0*|1*)0(01)*
答案D
解析 将NFA转换为DFA一般采用子集法。下面我们用子集法来进行转换。
   首先：K0=ε-closure(0)={S，1，2，3}，这是初始集，也就是初始状态。这里值得注意的一点是图中ε表示空，从S到1是ε箭头线，所以如果能到达S，也就能到达1。所以图6-6的初态实际上包含S，1，2，3四个。所以在表2-1中，第一行第一列是：{S，1，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/DXTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

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