java - 在java中表示转换函数的方法？

Question

我正在编写一个项目，将非确定性有限自动机转换为等效的确定性有限自动机。到目前为止，我已经有了 NFA 状态、字母表、起始状态和接受状态的 NFA.java 父类(super class)和子类以及各自的转换方法。到目前为止我的 NFA.java 类看起来像这样

class NFA {

    NFAStates statesNFA;
    NFAAlphabet alphabetNFA;
    NFASState startstateNFA;
    NFAAcceptStates acceptstatesNFA;

}

我的 NFAStates.java、NFAAlphabet.java 和 NFAAcceptStates.java 是从用户输入的数组中解析出来的字符串的 LinkedHashSet。我的 NFASState.java 类是一个包含单个字符的数组。

我正在尝试找到一种方法来准确存储转换函数(网格显示在某些输入下哪些状态进入哪个状态)。有没有办法可以做到这一点，也许使用 n 维数组？我还需要能够使用 DFA 中的方法操作该对象。

Answer 1

更一般地说，您要问的是如何表示具有节点和节点之间有向边的网络。在您的情况下，节点是状态，边缘是转换。因此，我将在下面的答案中使用您的术语，但您也可以轻松使用节点和边缘、城市和道路等。

根据您的问题空间的不同特征，您有多种选择。这些假设转换没有特征(例如成本、先决条件等)，但如果有，则模型的微小更改将支持存储这些特征。

1. 存储状态转换:

class State {
    private Set<State> transitions;
}

将转换存储在单独的类中

class Transition {
    private State from;
    private State to;
}

Set<Transition> transitions;

拥有从每个州到允许的下一个州的 map

Map<State, List<State>> transitions;

有一个 boolean 数组，表示是否允许每个状态更改(假设每个状态都有一个可用于索引数组的 ID)。

boolean[][] transitions;

您选择哪一个将取决于您从 NFA 转换到 DFA 时将使用的算法。我怀疑如果转换不在状态内，那么可能会排除选项 1 ，这会更容易。但重置可能对您来说都是可行的。只需选择最适合您的算法的一个即可。