我有一个关于有限状态机的紧迫问题，即我们如何知道这种语言需要 2 个状态或 3 个状态？我的意思是有什么公式吗？ 尽管我相信，我们始终会努力减少状态数量，但仍然如何根据任何语言或字符串确定要创建的状态数量(无需实际构建 DFA)？
最佳答案
您实际上是在询问DFA 最小化。这是一个经过充分研究的问题，已经开发了许多算法。 Wikipedia article这是一个很好的起点。
控制状态数量的理论结果是 Myhill-Nerode theorem ，但这个定理没有给出任何快速公式。您必须确定根据语言定义的等价关系中的等价类的数量。 Hopcroft 的 DFA 最小化算法本质上是一种用于确定 Myhill-Nerode 等价关系中的等价类的算法。我怀疑任何更直接地使用 Myhill-Nerode 的尝试都会导致类似于 Hopcroft 算法的结果，尽管我不是该领域的专家。
关于finite-automata - 如何根据任意语言确定有限自动机的状态数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33803587/