编译原理NFA->DFA (版权胡守杰，转载注明出处）

word数学符号无法显示，故导出网页pdf，网页地址：https://www.jianshu.com/p/3fb0b2e2b022

---

题目.png

---

设NFA M = {K，, f, S, Z},其中，
K={0,1,2,3,4,5,6,7,8,9,10}
={a,b}
S={1}
Z={10}
f = f(, ) = {} 其中 , ,

设：DFA N的状态集C={T0，T1…Ti}是NFA状态集K的子集
T0 = -closure(S) = {1,2,4}
T1=-closure(move(T0,a)) = {2,3,4,5}
T2=-closure(move(T0,b))={2,3,4,6}
T3=-closure(move(T1,a))={2,3,4,5,7,8,10}
T4=-closure(move(T1,b))={2,3,4,6} = T2
T5=-closure(move(T2,a))={2,3,4,5}=T1
T6=-closure(move(T2,b))={2,3,4,6,7,8,10}
T7=-closure(move(T3,a))={2,3,4,5,7,8,10}=T3
T8=-closure(move(T3,b))={2,3,4,6,8,9,10}
T9=-closure(move(T6,a))={2,3,4,5,8,9,10}
T10=-closure(move(T6,b))={2,3,4,6,8,9,10}=T8
T11=-closure(move(T8,a))={2,3,4,5,8,9,10}=T9
T12=-closure(move(T8,b))={2,3,4,6,8,9,10}=T8
T13=-closure(move(T9,a))={2,3,4,5,7,8,9,10}
T14=-closure(move(T9,b))={2,3,4,6,8,9,10}=T8
T15=-closure(move(T13,a))={2,3,4,5,7,8,9,10}=T13
T16=-closure(move(T13,b))={2,3,4,6,8,9,10}=T8

最后得：C={T0,T1,T2,T3,T6,T8,T9,T13}

所以：DFA N={C, {a,b}, f,{T0}, {T13}}

其中：
f(T0,a) = T1
f(T0,b) = T2
f(T1,a) = T3
f(T1,b) = T2
f(T2,a) = T1
f(T2,b) = T6
f(T3,a) = T3
f(T3,b) = T8
f(T6,a) = T9
f(T6,b) = T8
f(T8,a) = T9
f(T8,b) = T8
f(T9,a) = T13
f(T9,b) = T8
f(T13,a) = T13
f(T13,b) = T8

令T0,T1,T2,T3,T6,T8,T9,T13 分别为 0 , 1, 2, 3, 4, 5, 6, 7则有

DFA.png