NFA與DFA相比的優缺點？

NFA優於DFA：表示使用較少的內存。NFA與DFA相比的優缺點？

與NFA相比NFA的缺點：較慢地達到答案。

有沒有其他的優點或缺點？

2011-02-04 crowso

內存和速度之間的折衷？這是聞所未聞的！ – 2011-02-04 03:10:51

我認爲你已經完全掌握了主要的權衡。 NFA可以具有更高的內存效率，因爲它們可以在O（n）空間中編碼O（2 ⁿ）不同的配置，而同一語言的DFA可能需要指數空間。你同樣正確，NFA有更慢的更新;大多數用於模擬NFA的算法花費O（n）時間來計算DFA的狀態轉換（其中n是狀態數）與O（1）時間。

這兩者之間還有一些其他差異。對於初學者來說，DFA通常更易於編碼，因爲對於每一對狀態和符號，都只有一個轉換。這自然適用於轉換表的多維數組。相比之下，NFA（或更糟糕的，ε-NFA）通常需要更復雜的表示，因爲任何狀態都可能有大量的轉換。然而，NFA確實具有這樣的優點，即使用NFA從複雜結構到自動機的許多轉換更簡單。例如，從正則表達式中匹配自動機的規範構造會生成一個ε-NFA而不是DFA，因爲轉換最好是通過遞歸地構建更小的＆ε-NFA，然後使用＆epsilon;將它們連接在一起來表示。可以直接將正則表達式轉換爲DFA，但這樣做要困難得多。類似地，通過探索句柄識別自動機如何在NFA方面而非在DFA方面工作，許多用於生成LR（k）解析器的算法可以被更直觀地激勵（儘管用於生成這些解析器的大多數算法直接去往DFA而不是NFA ）。

希望這會有所幫助！

來源

2011-02-04 03:28:36 templatetypedef

NFA表示更緊湊，但DFA更易於模擬。當NFA減少到DFA時，通常情況下指數大小會增加

來源

2011-02-04 03:29:33

NFA與DFA相比的優缺點？

回答

相關問題