NFA确定化

1. DFA字母表与NFA相同(a,b)

2、构造DFA的初始状态(NFA的初始状态的ξ闭包)

ξ—closure({0})={0,1,2,4,7}
3 构造转换函数和其他状态
ξ—closure(MOVE([S1,S2,….Sj],a))=[R1,R2,…Rj]

  a b
0,1,2,4,7                     T0 3,8,6,7,1,2,4           T1 5,6,7,1,2,4             T2
3,8,6,7,1,2,4               T1 3,8,6,7,1,2,4           T1 9,5,6,7,1,2,4          T3
5,6,7,1,2,4                  T2 3,8,6,7,1,2,4           T1 5,6,7,1,2,4             T2
9,5,6,7,1,2,4               T3 3,8,6,7,1,2,4           T1 5,10,6,7,1,2,4        T4
5,10,6,7,1,2,4             T4* 3,8,6,7,1,2,4           T1 5,6,7,1,2,4             T2

T0表示起始状态,T4表示终止状态

原文地址:https://www.cnblogs.com/huhaijie1/p/12577512.html