非最小DFA的性能特徵

關於最小化DFA的算法的性能已經寫了很多。這令我的Google-fu感到沮喪，因爲這不是我想要的。非最小DFA的性能特徵

我們可以說一般關於非最小DFA的性能特徵嗎？我的直覺是，相對於輸入的長度，非最小DFA的運行時間仍然是O（n）。看起來最小化只會影響狀態的數量，從而影響存儲需求。它是否正確？

如果我們知道一些關於構建DFA的NFA的結構，我們是否可以改進泛化？例如，假設NFA完全是通過將連接，聯合和Kleene星操作應用於匹配任一輸入符號或epsilon的基本自動機來構造的。無法刪除轉換或創建任意轉換，我認爲不可能存在任何死鎖狀態。我們可以對從這些NFA構建的DFA做出什麼樣的概括？我對理論和經驗都有興趣。

來源

2015-01-13 Kevin Krumwiede

這個問題可以看作是題外話，可能更適合於http://cs.stackexchange.com/ – Codor

關於您的第一個問題，關於非最佳DFA的運行時間。純粹從理論上講，你應該仍然以O（n）運行的直覺是正確的。然而，設想（作爲一個例子），用於所述的Kleene星操作者以下僞代碼：

// given that the kleene-star operator starts at i=something 
while string[i] == 'r': 
    accepting = true; 
    i++; 
while string[i] == 'r': 
    accepting = true; 
    i++; 
// here the testing of the input string can continue for i+1

正如你可以看到，前兩個while循環是相同的，並且可被理解爲一個冗餘狀態。然而，「分裂」while循環會降低（除其他外）分支預測精度，因此也會降低整體運行時間（請參閱Mysticial關於分支預測的精彩解釋以獲取更多詳細信息：here。

許多其他類似的「實際」就是爲什麼非優化的DFA會更慢;其中，正如你所提到的那樣，更高的內存使用率（在很多情況下，更多的內存意味着更慢，因爲內存是 - 比較 - 是計算機的一個較慢部分）;對於每個附加狀態，更多的「ifs」需要對其後繼者進行輸入檢查;可能會有更多的循環（如示例中所示），這會使算法不僅在分支預測的基礎上變慢，而且僅僅因爲某些編程語言非常慢慢循環。

關於你的第二個問題 - 在這裏我不確定你的意思。畢竟，如果您正確地進行轉換，您應該首先獲得相當優化的DFA。

編輯：在討論中提出的想法是，可以有一個由一個NFA構建的非最小DFA，其效率會有所不同（無論選擇何種方式），而不是在實現中，而是在DFA。這是不可能的，因爲只有一個最佳的DFA。這是此示例的大綱：

假設我們創建和最小化DFA的過程是最佳的。
應用程序時，我們將首先構建一個DFA。在這一步中，我們可以創建無限多個等價狀態。這些狀態都以某種方式連接到NFA的圖表。
在下一步我們消除所有不可達狀態。這對性能無關緊要，因爲不可達狀態將對應於「死代碼」 - 永遠不會被執行。
在第四步中，我們通過分組等效狀態來最小化DFA。這就是它變得有趣的地方 - 因爲這個想法是我們可以用不同的方式做到這一點，從而產生不同的性能不同的DFA。但是，我們唯一的「選擇」是將狀態分配給不同的組。因此，出於理由，我們認爲我們可以做到這一點。但是，通過最小化算法背後的想法，我們只能對等值狀態進行分組。因此，如果我們對特定的國家進行分組的不同選擇，通過等價性的傳遞性，不僅國家將等同於兩個羣體，而且這些羣體也是等同的。因此，如果我們可以進行不同的分組，那麼算法將不是最優的，因爲它將組中的所有狀態放在一個組中。因此，可以有不同的最小化的假設必須是錯誤的。

來源

2015-01-13 20:12:52 cleros

你的答案的最後一句話基本上是我的意思。我正在尋求縮小「正確」和「非常優化」的含義。 –

對不起，我這方面很sl。。沒有「非常優化」 - 只有最佳。爲了DFA的最優性 - 在維基百科上廣泛地回答（搜索「確定性有限自動機」和「DFA最小化」，或者如果這還不夠，在許多書中（例如羅森稱之爲離散數學的入門更基本的一個，或者Hopcroft對自動機理論的介紹，以進行更徹底和苛刻的研究） – cleros

嗯，我確定有一定程度的最優性，我想知道是否有可能描述（甚至概率上）非最優性一個由NFA構建的DFA是以某種方式構建的，這可能意味着最佳的最小化策略，或者說它不值得最小化。 –

推理輸入接受的「運行時」將是相同的，因爲通常輸入的一個字符被消耗;在DFA的背景下，我從未聽過「運行時」這個概念（在漸近運行時複雜度的意義上）。最小化旨在最小化DFA的狀態數量（即優化「實施規模」）。

來源

2015-01-13 20:04:12 Codor

非最小DFA的性能特徵

回答

相關問題