NFA到DFA的轉化（保證能講明白）

如何將下圖的NFA轉化為DFA呢？

圖1

解答如下:

1. 求出 ε _ c l o s u r e ( s ) ε\_closure(s) ε_closure(s)
   ε _ c l o s u r e ( s ) ε\_closure(s) ε_closure(s)表示由狀態 s s s 經由條件 ε ε ε 可以到達的所有狀態的集合

ε _ c l o s u r e ( 0 ) = { 0 , 1 , 2 , 4 , 7 } ε\_closure(0)=\{0,1,2,4,7\} ε_closure(0)={0,1,2,4,7}
ε _ c l o s u r e ( 1 ) = { 1 , 2 , 4 } ε\_closure(1)=\{1,2,4\} ε_closure(1)={1,2,4}
ε _ c l o s u r e ( 2 ) = { 2 } ε\_closure(2)=\{2\} ε_closure(2)={2}
ε _ c l o s u r e ( 3 ) = { 1 , 2 , 3 , 4 , 6 , 7 } ε\_closure(3)=\{1,2,3,4,6,7\} ε_closure(3)={1,2,3,4,6,7}
ε _ c l o s u r e ( 4 ) = { 4 } ε\_closure(4)=\{4\} ε_closure(4)={4}
ε _ c l o s u r e ( 5 ) = { 1 , 2 , 4 , 5 , 6 , 7 } ε\_closure(5)=\{1,2,4,5,6,7\} ε_closure(5)={1,2,4,5,6,7}
ε _ c l o s u r e ( 6 ) = { 1 , 2 , 4 , 6 , 7 } ε\_closure(6)=\{1,2,4,6,7\} ε_closure(6)={1,2,4,6,7}
ε _ c l o s u r e ( 7 ) = { 7 } ε\_closure(7)=\{7\} ε_closure(7)={7}
ε _ c l o s u r e ( 8 ) = { 8 } ε\_closure(8)=\{8\} ε_closure(8)={8}
ε _ c l o s u r e ( 9 ) = { 9 } ε\_closure(9)=\{9\} ε_closure(9)={9}

2. 下面的A,B,C…表示一種狀態，如A表示 { 0 , 1 , 2 , 4 , 7 } \{0,1,2,4,7\} {0,1,2,4,7},其實就是 ε _ c l o s u r e ( 0 ) ε\_closure(0) ε_closure(0)

為了讀懂下面的內容，在這里先解釋幾個東西，

1. ε _ c l o s u r e ( m o v e ( A , a ) ) ε\_closure(move(A,a)) ε_closure(move(A,a)) 中的 m o v e ( A , a ) move(A,a) move(A,a)是什么意思呢？
   它代表從狀態A，經過a到達的狀態，
   A狀態是 ε _ c l o s u r e ( 0 ) = { 0 , 1 , 2 , 4 , 7 } ε\_closure(0) = \{0,1,2,4,7\} ε_closure(0)={0,1,2,4,7}，在 { 0 , 1 , 2 , 4 , 7 } \{0,1,2,4,7\} {0,1,2,4,7}里面，對每一個元素都考慮其是否通過a到達了某個狀態，觀察一下圖1，只有狀態2和7經過了a，分別到達了3和8，所以 m o v e ( A , a ) move(A,a) move(A,a) = { 3 , 8 } \{3,8\} {3,8}，從而有 ε _ c l o s u r e ( m o v e ( A , a ) ) = ε _ c l o s u r e ( { 3 , 8 } ) = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } ε\_closure(move(A,a)) = ε\_closure(\{3,8\}) = \{1,2,3,4,6,7,8\} ε_closure(move(A,a))=ε_closure({3,8})={1,2,3,4,6,7,8}， { 1 , 2 , 3 , 4 , 6 , 7 , 8 } \{1,2,3,4,6,7,8\} {1,2,3,4,6,7,8}是未出現過的狀態，所以可把它取名為B狀態(其它名字也行).
2. ε _ c l o s u r e ( { 3 , 8 } ) = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } ε\_closure(\{3,8\}) = \{1,2,3,4,6,7,8\} ε_closure({3,8})={1,2,3,4,6,7,8}是怎么來的呢？
   因為在步驟1我們已經知道， ε _ c l o s u r e ( 3 ) = { 1 , 2 , 3 , 4 , 6 , 7 } ε\_closure(3)=\{1,2,3,4,6,7\} ε_closure(3)={1,2,3,4,6,7}， ε _ c l o s u r e ( 8 ) = { 8 } ε\_closure(8)=\{8\} ε_closure(8)={8} ，然后取它們的并集就得到了 { 1 , 2 , 3 , 4 , 6 , 7 , 8 } \{1,2,3,4,6,7,8\} {1,2,3,4,6,7,8}.
   
   這樣應該解釋明白了，繼續往下看，然后不懂的話再倒回來看看，

ε _ c l o s u r e ( 0 ) = { 0 , 1 , 2 , 4 , 7 } = A ε\_closure(0) = \{0,1,2,4,7\} = A ε_closure(0)={0,1,2,4,7}=A
ε _ c l o s u r e ( m o v e ( A , a ) ) = ε _ c l o s u r e ( { 3 , 8 } ) = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } = B ε\_closure(move(A,a)) = ε\_closure(\{3,8\}) = \{1,2,3,4,6,7,8\} = B ε_closure(move(A,a))=ε_closure({3,8})={1,2,3,4,6,7,8}=B
ε _ c l o s u r e ( m o v e ( A , b ) ) = ε _ c l o s u r e ( 5 ) = { 1 , 2 , 4 , 5 , 6 , 7 } = C ε\_closure(move(A,b)) = ε\_closure(5) = \{1,2,4,5,6,7\} = C ε_closure(move(A,b))=ε_closure(5)={1,2,4,5,6,7}=C
ε _ c l o s u r e ( m o v e ( B , a ) ) = ε _ c l o s u r e ( { 3 , 8 } ) = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } = B ε\_closure(move(B,a)) = ε\_closure(\{3,8\}) = \{1,2,3,4,6,7,8\} = B ε_closure(move(B,a))=ε_closure({3,8})={1,2,3,4,6,7,8}=B
ε _ c l o s u r e ( m o v e ( B , b ) ) = ε _ c l o s u r e ( { 5 , 9 } ) = { 1 , 2 , 4 , 5 , 6 , 7 , 9 } = D ε\_closure(move(B,b)) = ε\_closure(\{5,9\}) =\{1,2,4,5,6,7,9\} = D ε_closure(move(B,b))=ε_closure({5,9})={1,2,4,5,6,7,9}=D
ε _ c l o s u r e ( m o v e ( C , a ) ) = ε _ c l o s u r e ( ) ε\_closure(move(C,a)) = ε\_closure() ε_closure(move(C,a))=ε_closure()
ε _ c l o s u r e ( m o v e ( C , b ) ) = ε _ c l o s u r e ( 5 ) = { 1 , 2 , 4 , 5 , 6 , 7 } = C ε\_closure(move(C,b)) = ε\_closure(5) = \{1,2,4,5,6,7\} = C ε_closure(move(C,b))=ε_closure(5)={1,2,4,5,6,7}=C
ε _ c l o s u r e ( m o v e ( D , a ) ) = ε _ c l o s u r e ( { 3 , 8 } ) = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } = B ε\_closure(move(D,a)) = ε\_closure(\{3,8\}) = \{1,2,3,4,6,7,8\} = B ε_closure(move(D,a))=ε_closure({3,8})={1,2,3,4,6,7,8}=B
ε _ c l o s u r e ( m o v e ( D , b ) ) = ε _ c l o s u r e ( 5 ) = { 1 , 2 , 4 , 5 , 6 , 7 } = C ε\_closure(move(D,b)) = ε\_closure(5) = \{1,2,4,5,6,7\} = C ε_closure(move(D,b))=ε_closure(5)={1,2,4,5,6,7}=C

3. 畫出DFA狀態轉換表
   步驟2中有A,B,C,D四種情況，其中A是初始情況（ ε _ c l o s u r e ( 0 ) = { 0 , 1 , 2 , 4 , 7 } ε\_closure(0)=\{0,1,2,4,7\} ε_closure(0)={0,1,2,4,7}. 多說幾句，在NFA圖1中，是從0出發的，所以初始情況是 ε _ c l o s u r e ( 0 ) ε\_closure(0) ε_closure(0)，那假設如果是從X開始，則初始情況是 ε _ c l o s u r e ( X ) ε\_closure(X) ε_closure(X)）

看步驟2， ε _ c l o s u r e ( m o v e ( A , a ) ) = ε _ c l o s u r e ( { 3 , 8 } ) = { 1 , 2 , 3 , 4 , 6 , 7 , 8 } = B ε\_closure(move(A,a)) = ε\_closure(\{3,8\}) = \{1,2,3,4,6,7,8\} = B ε_closure(move(A,a))=ε_closure({3,8})={1,2,3,4,6,7,8}=B，所以A行a列填B，其他同理，

4. 根據DFA狀態轉換表畫出DFA狀態轉換圖

看步驟3的表格，A經過a到B，A經過b到C，B經過a到B，以此類推…

參考：
NFA到DFA的轉化🔗