12

众所周知,如何从常规语言的 NFA 到最小 DFA。但是,DFA 可能具有成倍增加的状态数。

我需要的是一种减少 NFA 的方法,再次给出 NFA 但状态数量较少。我不需要结果是确定性的,但我希望它尽可能小,同时保留公认的语言(也许不是绝对最优,但越小越好)。

这个问题的最佳算法是什么?或者也许不是“最好的”,但至少是“最容易以非糟糕的效率实施”?或者问题是否有一个众所周知的名称,以便我自己可以找到好的信息来源?

4

2 回答 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 回答