未確定的NFA最小化

Question

衆所周知，如何從常規語言的NFA獲得最小DFA。但是，DFA的狀態數可能會呈指數級增長。

我需要的是一種減少NFA的方法，再次給出一個NFA但帶有一個較小的個狀態。 T.I.我不需要結果是確定性的，但我希望它儘可能小，同時保留公認的語言（可能不是絕對最佳，但更小，更好）。

這個問題最好的算法是什麼？或者可能不是「最好的」，但至少「最容易實現，效率不高」？ 還是問題有一個衆所周知的名稱，以便我可以找到自己的良好信息來源？

Answer 1

我相信這個問題也被稱爲NFA最小化。我相信這是一般的NP-hard。

一個富有成效的方法可能是最小化Bisimulation [Paige，Tarjan 1987]以及後續的衍生物。

This presentation有一些關於這個問題的易處理性的說明，以及一些方法的參考，其中列出了它們的相對優點。

Answer 2

還有的龜田 - 韋納算法NFA這裏最小化的實現：https://github.com/coder0xff/parlex/blob/master/IDE/Nfa.cs