java - DFA 字符串验证

Question

我有一个程序，它简单地将所有状态作为一组状态作为输入。然后下一个输入是状态集合中的初始状态，然后是最终状态集合。

接下来是我在各州之间进行的一组转换。

例如：q0,1,q1

这意味着在输入 1 上存在从 q0 到 q1 的转换。

对于每个状态，都会输入转换。

但是在这里我面临的是可以以随机方式跳转引用，即转换可以是非重复字符的 n 次转换，因此我想动态地为每个状态维护一个 hashmap 对象。

我怎样才能做到这一点？

Answer 1

由于这是一个 DFA，因此维护从（状态，输入）对到结果状态的单个哈希图可能更容易和更有效。DFA 属性保证了转换关系可以以这种方式被视为一个函数。

因此，为您给出的示例维护一个HashMap<StateInput, State> trans并执行，其中trans.put(StateInput(q0, 1), q1)

class StateInput {
    public State state;
    public int input;
}

Answer 2

像这样的东西，也许？

class State {
  private Map<State, Character> transitions;

  // ...

  public void addTransition(State nextState, Character input) {
     transistions.put(nextState, input);
  }

  // ...
}