众所周知，人们是如何从一种常规语言的NFA转换为最低DFA的。但是，DFA的州数量可能成倍增加。
我需要的是减少NFA的方法，再次提供NFA，但州数较少。 T.i.我不需要确定的结果，但我希望它在保留公认的语言的同时尽可能小(也许不是绝对最佳，但越小越好)。
解决此问题的最佳算法是什么？也许不是“最好的”，而是至少“最容易实现且效率极高的”？
还是该问题的名字众所周知，以便我自己可以找到很好的信息来源？
最佳答案
我相信这个问题也被称为NFA最小化。我相信，这通常是NP难题。
一种富有成果的方法可能是Bisimulation Minimization [Paige，Tarjan 1987]和后续的衍生方法。
This presentation对问题的易处理性进行了一些注释，并提及了一些方法及其相对优点。
关于regex - NFA最小化而不确定，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3379051/