问题 单项选择题

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

表2-1 状态集表

状态集T1中不包括编号为 (23) 的状态;状态集T2中的成员有 (24) :状态集T3等于 (25) ;该自动机所识别的语言可以用正规式 (26) 表示。

(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={},据此可以得出答案。

填空题
问答题 简答题