NFA轉換爲DFA

當我們從nfa轉換爲dfa時，可能會出現如下圖所示的結果...我的問題是，是否有必要從狀態{4}寫入它是否爲零狀態？我的意思是沒有顯示{4}的輸入符號1與右下方的圖片相同？或沒有？NFA轉換爲DFA

enter image description here

2012-06-04 a1204773

這是一個約定的問題。就個人而言，我不希望將DFA與不必要的狀態混雜在一起，尤其是因爲通過從NFA轉換獲得的DFA往往變得相當複雜，並且由於它是確定性的，我們知道任何未顯示的轉換必須是無效的。

但是，我經歷過許多學術界人士教/使用其他約定，並要求明確顯示所有轉換。當我作爲TA（導師）工作時，我實際上已經和一位教授討論了這個問題 - 他希望我們的導師在最終測試中扣除DFA失蹤過渡期的點數，但是我說服他，扣除點數是不公平的。

2012-06-04 21:19:42

謝謝@konrad，我不想失去指出這樣的事情，所以我會寫它......但我同意你的這是不必要的 – a1204773

沒有必要寫{4} - > 0的跳變，因爲自動機已經被接受的單詞。這種轉變意味着這隻對我們的解決方案「沒有任何意義」。但是有關詳細信息，請參閱它以顯示整個自動機。

2012-06-04 21:11:30 doniyor

這是不正確的。上述自動機將*不*接受輸入0001，但它將接受000.是否需要顯示轉換到空狀態是一個約定的問題，但你的答案使它聽起來好像0001會被自動機接受有什麼關係。 –

不，這不是我的意思。我的意思是，直到（包括）{4}的轉換都接受除......之外的所有單詞（所有單詞直到{4} - 狀態包含）。我們知道{4}之後的轉換不能決定解決方案，所以給出這個最後的1轉換對於解決方案來說並不是必要的。 – doniyor

是的，我認爲也一樣.. – a1204773

只有在您試圖繪製MinimalFA（MFA）時才重要。
實際上，您可以從單個NFA生成無限數量的DFA，每個NFA的狀態數量都不相同。
如果您在圖中刪除'Dead States'，您將獲得MFA。如果你只想要一個DFA，這個數字就沒有問題

2013-07-18 15:48:05 dvs

回答