NFA到DFA的转换过程

1．具有ε动作的NFA状态转换表

0 1 2 3 4 5 6 7 8 9

a Φ Φ 3 Φ Φ Φ Φ 8 Φ Φ b Φ Φ Φ Φ 5 Φ Φ Φ 9 Φ ε 1, 7 2, 4 Φ 6 Φ 6 1, 7 Φ Φ Φ 2．分别求ε-closure

εεεεεεεεεε

-closure(0) = {0,1,2,4,7} -closure(1) = {1,2,4} -closure(2) = {2}

-closure(3) = {1,2,3,4,6,7} -closure(4) = {4}

-closure(5) = {1,2,4,5,6,7} -closure(6) = {1,2,4,6,7} -closure(7) = {7} -closure(8) = {8} -closure(9) = {9}

3．转换算法：

εεεεεεεεε

-closure(0) = {0,1,2,4,7} = A

-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8} = B -closure(move(A,b))=ε-closure({5})={1,2,4,5,6,7} = C -closure(move(B,a))=ε-closure({3,8}) = B

-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9} = D -closure(move(C,a))=ε-closure({3,8}) = B -closure(move(C,b))=ε-closure({5}) = C -closure(move(D,a))=ε-closure({3,8}) = B -closure(move(D,b))=ε-closure({5}) = C

4．DFA的转换表

状态 A B C D 输入符号 a B B B B b C D C C

5．状态转换图