众所周知，如何从常规语言的 NFA 到最小 DFA。但是，DFA 可能具有成倍增加的状态数。
我需要的是一种减少 NFA 的方法，再次给出 NFA 但状态数量较少。我不需要结果是确定性的，但我希望它尽可能小，同时保留公认的语言（也许不是绝对最优，但越小越好）。
这个问题的最佳算法是什么？或者也许不是“最好的”，但至少是“最容易以非糟糕的效率实施”？或者问题是否有一个众所周知的名称，以便我自己可以找到好的信息来源？
问问题
1958 次
2 回答
9
我相信这个问题也被称为 NFA 最小化。我相信，这通常是 NP 难的。
一种富有成效的方法可能是 Bisimulation Minimization [Paige, Tarjan 1987]，以及随后的衍生方法。
该演示文稿对问题的易处理性有一些注释，并引用了一些方法并阐明了它们的相对优点。
于 2010-07-31T17:16:52.247 回答
2
这里有一个用于 NFA 最小化的 Kameda-Weiner 算法的实现：https ://github.com/coder0xff/parlex_legacy/blob/132e4a23a599140d22b18ead832626f0c607340f/Automata/NFA.cs#L641
于 2013-08-24T23:58:36.057 回答