DFA Minimization Brzozowski算法

我正在嘗試實現Brzozowski的算法以最小化我的DFA 以下是相同的算法。DFA Minimization Brzozowski算法

DFA = d(r(d(r(NFA))))

其中r()是NFA和D()的反轉轉換NFA到DFA。

但我不明白r()在google上搜索的含義也沒有提供太多的信息。

有誰能解釋一下NFA的r()是什麼。

任何其他簡單的算法或C++實現可用請讓我知道鏈接。

2011-05-05 Avinash

在reverse.c的代碼中（找到~~here~~，但現在已不存在），您會發現評論/* Create reversed edges */。所以我認爲r()是反轉所有邊緣的方向（加上確保反轉自動機具有明確的啓動狀態）。

2011-05-05 07:16:43

在提出問題之前，我曾看過您的博客。你能幫我理解NFA的概念是什麼意思嗎？這是否意味着如果從狀態S1轉換到S2，它變成S2到S1以及所有最終狀態和非最終狀態發生了什麼。 – Avinash 2011-05-05 07:21:25

這不是我的博客，但是，我從代碼中得到的印象正是你所說的。在'/ *創建新的開始狀態* /'之後查看'case'語句時，我感覺代碼（reverse.c）創建了一個新的開始狀態並將其連接到原始NFA的所有結束狀態通過一個epsilon過渡。 – 2011-05-05 07:29:16

最終狀態和非最終狀態會發生什麼。 – Avinash 2011-05-05 07:41:02

This是OpenFst的實現。

在this紙是顯示應用反轉操作的結果的圖（第15頁）。

幫助理解FSM操作的一種更簡單的方法是使用像OpenFst這樣的庫來創建和操作機器，然後使用Graphviz可視化結果。

2011-05-05 08:49:08

回答