7

我正在开发一个将非确定性有限状态自动机 (NFA) 转换为确定性有限状态自动机 (DFA) 的程序。为此，我必须计算 NFA 中每个具有 epsilon 转换的状态的 epsilon 闭包。我已经想出了一种方法来做到这一点，但我总是认为我首先想到的通常是做某事效率最低的方法。

这是我如何计算简单的 epsilon 闭包的示例：

转换函数的输入字符串：格式为 startState，symbol = endState

EPS 是一个 epsilon 转换

1，每股收益 = 2

结果在新状态 { 12 }

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

4

4 回答 4

4

在边缘是您的 epilson 转换的图上进行深度优先搜索（或广度优先搜索 - 并不重要）。所以换句话说，如果您有效地跟踪您已经添加到闭包中的状态，您的解决方案是最佳的。

于 2011-02-14T10:33:50.620 回答
3

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

于 2011-02-14T18:45:27.260 回答
0

你看过算法书吗？但我怀疑你会找到更好的方法。但是这个算法的实际性能很可能取决于你用来实现你的图的具体数据结构。您可以共享工作，具体取决于您简化图表的顺序。考虑一下 epsilon 连接并从两个不同节点引用的子图。我不确定这是否可以以最佳方式完成，或者您是否必须求助于一些启发式方法。

浏览有关算法的文献。

于 2011-02-14T11:21:26.787 回答
0

只是为了让只寻找@Xodarap 的答案引用的特定代码片段的人不会发现自己需要下载源代码和应用程​​序来查看 jar 文件的代码，我冒昧地附上所述片段。

public static State[] getClosure(State state, Automaton automaton) {
    List<State> list = new ArrayList<>();
    list.add(state);
    for (int i = 0; i < list.size(); i++) {
        state = (State) list.get(i);
        Transition transitions[] = automaton.getTransitionsFromState(state);
        for (int k = 0; k < transitions.length; k++) {
            Transition transition = transitions[k];
            LambdaTransitionChecker checker = LambdaCheckerFactory
                    .getLambdaChecker(automaton);
            /** if lambda transition */
            if (checker.isLambdaTransition(transition)) {
                State toState = transition.getToState();
                if (!list.contains(toState)) {
                    list.add(toState);
                }
            }
        }
    }
    return (State[]) list.toArray(new State[0]);
}

不用说，所有功劳都归功于 @Xodarap 和 JFLAP 项目。

于 2021-07-01T14:45:29.990 回答