什麼是McNaughton-Yamada算法？

Question

我需要爲CS類使用McNaughton-Yamada算法構建DFA。問題是算法是補充材料，我不清楚它究竟是什麼。這是一種找到給定RegEx的DFA或找到DFA並將其最小化的方法嗎？我似乎無法找到關於此主題的任何信息。

我很困惑，因爲我們的教師在課堂上發現DFA之後顯示的最小化例程與我們的book中描述的「標記」最小化似乎沒有任何不同。

感謝您的回覆，

森

Answer 1

「... McNaughton-Yamada分析算法，通過該算法可以找到一個正則表達式來描述被​​給定了轉換表的有限狀態機所接受的字。未經修改的算法將產生4n個表示n狀態機的項。通過消除重複的計算並在相同的狀態圖上拒絕對應於不可能的路徑的高級表達式，可以減少該數量。其餘的表達式帶來了嚴重的簡化問題，因爲空算法產生了空表達式和空字。

Source

Answer 2

有該算法的描述（對於正則表達式來NFA和NFA到DFA）在http://swtch.com/~rsc/regexp/regexp1.html;他們展示了Thompson的版本，並聲稱McNaughton-Yamada算法基本相同，但直接從正則表達式生成DFA。

Answer 3

他們的算法通常不會帶來了從湯普森的工作分開。湯普森的原作從正則表達式轉變爲記憶中的模擬NFA。 Thompson-McNaughton-Yamada算法是將正則表達式轉換爲存儲在內存中的實際NFA的擴展，與瞬態仿真相反。

將NFA轉換爲DFA（確定性）不是McNaughton或Yamada擴展的一部分。相反，它是通過subset construction（aka powerset構建）算法完成的。

通過使用Compiler Construction Toolkit的regular expression to NFA and DFA工具，您可以看到Thompson-McNaughton-Yamada算法和子集構建算法在任意正則表達式上的作用。