计算epsilon闭包的最快方法是什么？

Question

我正在研究一种将非确定性有限状态自动机(NFA)转换为确定性有限状态自动机(DFA)的程序.为此,我必须计算具有epsilon转换的NFA中每个状态的epsilon闭包.我已经找到了一种方法来做到这一点,但我总是认为我想到的第一件事通常是效率最低的做事方式.

这是一个如何计算简单的epsilon闭包的例子:

转换函数的输入字符串:format是startState,symbol = endState

EPS是一个epsilon过渡

1,EPS = 2

新州的结果{12}

现在显然这是一个非常简单的例子.我需要能够从任意数量的状态计算任意数量的epsilon转换.为此,我的解决方案是一个递归函数,通过查看它具有epsilon转换的状态来计算给定状态的epsilon闭包.如果该状态具有(a)epsilon转换,则在for循环内递归调用该函数,以获得与其一样多的epsilon转换.这将完成工作,但可能不是最快的方法.所以我的问题是:在Java中计算epsilon闭包的最快方法是什么？

Answer 1

JFLAP就是这样做的。您可以查看它们的源代码- 特别是 ClosureTaker.java。这是深度优先搜索（这是 Peter Taylor 所建议的），并且由于 JFLAP 使用它，我认为这是接近最优的解决方案。