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

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

题目.png

设NFA M = {K， $\Sigma$ , f, S, Z},其中，
K={0,1,2,3,4,5,6,7,8,9,10}
$\Sigma$ ={a,b}
S={1}
Z={10}
f = f( $K_i$ , $\Sigma_j$ ) = { $K_k$ } 其中 $S_i \in K$ , $\Sigma_j \in \Sigma$ , $K_k \in K$

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

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

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

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

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

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

推荐阅读更多精彩内容