將DFA作爲鏈表執行的算法

Question

我想知道如何在C/C++/Java中將DFA實現爲鏈接列表。

Answer 1

因爲每個州可以有多個分支，您可能需要多個鏈接列表。這意味着，每個狀態都有一個n個鏈接列表。所以它更像是一個具有循環的樹結構而不是簡單的鏈表。

Answer 2

這是絕對有可能的，但是會非常低效。你要做的只是將所有狀態存儲在鏈接列表中，然後每個狀態都需要保留一個轉換表。轉換表看起來是這樣的：

'a' -> 2 
'b' -> 5 

您的字母是{a,b}，以及2和5存儲在鏈接的列表中的位置2和5的狀態。正如我所說的，這絕對不是您想要實現DFA的方式，但它是可能的。

Answer 3

，在我的腦海裏想出的第一件事是，

創建一個類/結構稱爲狀態有兩個陣列組件。一個是可以到達我們州的州，另一個是從我們州到達的州。 然後創建一個鏈接列表，其元素是您的狀態。

，這裏是我實現這個類

class state 
{ 
    private: 
     string stateName; 
     vector<state> states_before_me; 
     vector<state> states_after_me; 
     state* next; 

     //methods of this state 

} 

Answer 4

單鏈表不能有效代表DFA的。您可以將DFA視爲有向加權圖數據結構，因爲狀態是頂點，過渡是邊，過渡符號是權重。有兩種主要的方法來實現圖結構。

i）鄰接表：它基本上有V（頂點數）鏈表。每個鏈接列表包含具有對應頂點的邊的頂點。如果我們有頂點(1,2,3)和邊緣(1,2),(1,3),(2,1),(2,3),(3,3)對應adjanceny列表是：

1->2->3 
2->1->3 
3->3 

ⅱ）鄰接矩陣：這是一個VXV矩陣與位於（i，j）的每個條目從i象徵的邊緣至j。上述同樣的例子表示如下（1表示有邊緣，0意味着沒有）：

1 2 3 
1 0 1 1 
2 1 0 1 
3 0 0 1 

但是因爲你的圖進行加權，你必須做出一點改變這些。

對於列表實現，您可以將鏈接列表中的頂點更改爲包含頂點和連接這些頂點的邊的權重的結構。

對於矩陣實現，您可以將權重直接放入矩陣而不是0.1值。

如果你不想處理圖類的實現，有像Boost Graph Library這樣的庫包含兩個實現和所有重要圖算法DFS到Dijkstra的最短路徑算法。你可以從http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/index.html查找它。