具有 e動作的NFA到DFA確定化演算法

來自專欄 服務端編程-筆記

具有 e動作的NFA的確定化演算法

演算法：子集法

• 與不存在e的NFA不一樣，開始狀態在查找過程中，因為e的存在，遞歸進行a/b時會產生n個不確定的狀態鏈，需要對這些多個e組成的狀態鏈，在轉化為DFA過程中，轉換，去除。從而達到可以轉化成為DFA。也是必要條件。

演算法解析：

• 初始C={}；
• e-closure(0)的意思是：從位於0的開始狀態，經由任意條e弧而能到達的狀態的集合。所以 e-closure(0)={0,1,2,4,7}，{0,1,2,4,7}是新的唯一的狀態，加入到C集合中，用T0表示。T0=e-e-closure(0)={0,1,2,4,7}。
• 不能標識的意思：因為它是一個新的狀態，我們在轉化為DFA時，不能識別出它是已具有的與a,b前驅後繼的狀態，那麼DFA在轉化過程中，這個狀態沒辦法與a,b建立關係，這樣的後果是，a,b和這個狀態沒什麼連接關係。所以，針對新的不能識別的狀態，我們讓它參與到a,b的路徑定位運算。使得它可以成為一個能被DFA在轉化過程中所接受的一個狀態。
• Move(T0,a)意思是：在T0狀態集中，查找與a路徑相關的狀態的集合。
• 即：e-closure(move(T0,a)={0,1,2,3,4,6,7,8},先查找C集合中,有沒有對應的狀態，明顯沒有，所以再定義一個T1,T1=e-closure(move(T0,a)={0,1,2,3,4,6,7,8},(以e弧相關狀態為基礎求與a弧相關狀態的集合)。
• 參與完到a,的路徑定位運算後，接著b.
• e-closure(move(T0,b)={1,2,4,5,6,7}先查找C集合中,有沒有對應的狀態，明顯沒有，所以再定義一個T2,
• 此時C集合為{T0,T1,T2}
• T0參與完 a,b的路徑定位運算後。該T1。
• 所以接著讓T1也執行T0的操作，即T1查找與a弧相關的狀態集。
• e-closure(move(T1,a)={1,2,3,4,6,7,8},先查找C集合中,有沒有對應的狀態，發現對應於C集合中T1,即在DFA轉化過程中，可以找到與a,b弧對應的狀態標識。所以不需要再定義新的Ti,(i->1,2,3 ……)
• T1執行b
• e-closure(move(T1,b)={1,2,4,5,6,7,9},先查找C集合中,有沒有對應的狀態，明顯沒有，所以再定義一個T3,C={T0,T1,T2,T3};
• 接著讓T2執行操作，即T2查找與a，b弧相關的狀態集。
• e-closure(move(T2,a)={1,2,3,4,6,7,8},先查找C集合中,有沒有對應的狀態，發現對應於C集合的T1.
• T2執行b
• e-closure(move(T2,b)={1,2,4,5,6,7},查找C集合中, 發現對應於C集合的T2.
• 接著讓T3執行操作，即T3查找與a，b弧相關的狀態集。
• e-closure(move(T3,a)={1,2,3,4,6,7,8},查找C集合中, 發現對應於C集合的T1.
• e-closure(move(T3,b)={1,2,3,5,6,7,10},查找C集合中,有沒有對應的狀態，明顯沒有，所以再定義一個T4,C={T0,T1,T2,T3,T4};
• 接著讓T4執行操作，即T4查找與a，b弧相關的狀態集。
• e-closure(move(T4,a)={1,2,3,4,6,7,8},查找C集合中, 發現對應於C集合的T1.
• e-closure(move(T4,b)={1,2,4,5,6,7},查找C集合中, 發現對應於C集合的T2.

C集合查找新狀態對應完畢。

綜上信息歸納：M={S,E,D,S0,St}T0={0,1,2,4,7}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}T3={1,2,4,5,6,7,9}T4={1,2,4,5,6,7,10}S={[T0],[T1],[T2],[T3],T[4]}E={a,b}D([T0],a)= [T1]D([T0],b)= [T2]D([T1],a)= [T1]D([T1],b)= [T3]D([T2],a)= [T1]D([T2],b)= [T2]D([T3],a)= [T1]D([T3],b)= [T4]D([T4],a)= [T1]D([T4],a)= [T2]S0=[T0]St=[T4]

• 由上面推導的內容，就可以將NFA有e符號的弧，轉化為無符號的DFA。

未經允許，禁止轉載

推薦閱讀：