NFA與DFA的優點/缺點相反

Question

DFA和NFA的相對親和親分別是什麼？

我知道，DFA的相比，是容易NFA的和NFA的是慢比DFA的的接受狀態到達，但還有沒有其他明確的，衆所周知的優點/缺點實現？

Answer 1

NFA的超過DFA的優點是財產，始終「選擇正確的道路」。由於您無法在算法中選擇「選擇正確的路徑」，因此通常會將NFA轉換爲DFA，從而創建符號化多個NFA狀態的DFA狀態。因此，當您的NFA處於A狀態並且可以選擇轉到A，B或C時，您的DFA中的下一個狀態將爲{A，B，C}。

這解釋的優點和缺點： DFA的可以，因爲他們的下一個狀態是由功能決定實施更加容易。 NFA允許用戶更容易地表達他們想要的內容，因爲NFA可以在多個路徑之間進行選擇。

Answer 2

的NFA和DFA的接受同一組的語言 - 正規語言。

NFA（不是DFA，因爲DFA是NFA的一個子集）的直接實現通常涉及允許回溯，而直接實現DFA只需要與輸入長度一樣多的步驟，所以在這個意義上，DFA「比」等效的NFA（不是DFA）更快地得出答案。

當試圖找到對應於給定語言或RE（例如，通過一種算法）一個FA，它通常更容易在NFA首先到達（因爲規則是不太嚴格的）。當試圖證明FA的存在時尤其如此，因爲NFA的存在與DFA的存在一樣好。如果需要DFA，則存在以下算法（a）將NFA轉換爲等效的DFA和（b）將DFA最小化。

製作總概括的DFA更快但更復雜的（在狀態和轉換的數量而言），而是NFA的速度較慢，但​​更簡單的（在相同的條件）。

Answer 3

NFA超過DFA的一個明顯優勢是，您可以使用NFA輕鬆構建FA代表兩種（或更多）語言的聯合，交集，靜止等語言。也就是說，如果你有一些簡單的FA做部分工作，你可以使用NFA來輕鬆地組合他們。在使用DFA時，您需要建立一個自動完成所有工作的新自動機。

看，實施起來比較容易。 但你提到的時間問題。