我正在开发将非确定性有限状态自动机(NFA)转换为确定性有限状态自动机(DFA)的程序。为此，我必须计算NFA中具有ε过渡的每个状态的ε闭合。我已经想出了一种方法来执行此操作，但是我一直认为我想到的第一件事通常是做某事的效率最低的方法。
这是我如何计算简单的epsilon闭包的示例:
转换函数的输入字符串:格式为startState，symbol = endState
EPS是一个epsilon过渡
1，EPS = 2
结果进入新状态{12}
现在显然这是一个非常简单的示例。我将需要能够从任何数量的状态计算出任何数量的epsilon跃迁。为此，我的解决方案是一个递归函数，该函数通过查看给定状态的epsilon转换状态来计算给定状态的epsilon闭包。如果该状态有一个(或多个)ε跃迁，则在for循环中递归调用该函数，以获取尽可能多的ε跃迁。这样可以完成工作，但可能不是最快的方法。所以我的问题是:用Java计算epsilon闭包的最快方法是什么？
最佳答案
JFLAP执行此操作。您可以看到它们的source-特别是ClosureTaker.java。这是深度优先搜索(这是Peter Taylor所建议的)，并且由于JFLAP使用了该搜索，所以我认为这是近乎最佳的解决方案。
关于java - 计算epsilon闭合的最快方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4989991/