regex - 无确定化的 NFA 最小化

Question

众所周知，如何从常规语言的 NFA 到最小 DFA。然而，DFA 的状态数量可能呈指数增长。

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

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

Answer 1

我相信这个问题也被称为 NFA 最小化。我相信，这通常是 NP 难的。

一种富有成效的方法可能是互模拟最小化 [Paige, Tarjan 1987]，以及后续的衍生方法。

This presentation对问题的易处理性做了一些说明，并引用了一些方法，并阐明了它们的相对优点。