NFA到DFA算法

Question

我讀過一個符號，狀態和轉換的文本文件，並把它放在一張表中。它看起來像這樣：
符號A，B
狀態Q1，Q2，Q3，Q4
啓動狀態Q4
最終狀態Q2，Q3

過渡態：
Q4，ε，Q1
Q1，一，Q2
Q3，一，Q3
Q3，b，Q1

我讀過關於如何NFA轉換爲DFA，但我的算法不太瞭解算法。我將如何創建轉換方法以及我應該擁有什麼狀態類？

Answer 1

您是否有編程問題或Automata問題？

因爲編程它看起來很簡單。是的，你會有一個州級，有4個可能的值q1-a4。狀態類有一個構造函數將其初始化爲q4。它具有修改狀態對象的Accept（符號）函數，並且可能還有一個IsEndState（）函數，該函數對狀態q2和q3返回true。

NFA/DFA部分在Accept（）方法的實現中發揮作用。現在它可能是您被要求提供programmtic解決方案，將Accept（）的基於NFA的實現轉換爲Accept（）的基於DFA的實現。

Answer 2

我有在這裏一個漂亮的鏈接： JFLAP

JFLAP是一個Java的JAR其中包含有一些不錯的可視化。你可以測試和轉換NFAs/DFA，做Pummping引理的東西，並檢查各種語法和... 你可以試試看！

Answer 3

這兩個環節可以幫助你：

http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf

Answer 4

如果你想無需下載像JFLAP自動做到這一點，給Online NFA to DFA conversion tool旋轉。

ProfBrown's "Convert NFA to DFA" video on YouTube探討如何做到這一點在一些嚴謹，但國際海事組織是不切實際和不必要的繁瑣的有手工編寫的表了。當你習慣了這個過程時，你可以在小圖上看到它。在大圖的情況下，無論如何，您都可以使用工具來實現自動化。