A.(0|1)*B.(0*|1*)*001C.(0*|1*)*0(0|1)*D.(0*|1*)0(0|1)*

Question

A．(0｜1)*

B．(0*｜1*)*001

C．(0*｜1*)*0(0｜1)*

D．(0*｜1*)0(0｜1)*

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