当前位置：文江博客话题详情

DFA 字符串验证

发布于 2024-12-05 14:59:46 字数 286 浏览 2 评论 0原文

我有一个程序，只需将所有状态作为一组状态作为输入。然后采用的下一个输入是状态集中的初始状态，然后是最终状态集。

接下来是我在各州之间采取的一组过渡。

例如：q0,1,q1

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

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

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

我怎样才能实现这个目标？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

蓝眼泪 2024-12-12 14:59:46

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

因此，维护一个 HashMaptrans 并针对您给出的示例执行 trans.put(StateInput(q0, 1), q1) ，其中

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

Since this is a DFA, it may be easier and more efficient to maintain a single hashmap from (state, input) pairs to resulting states. The DFA properties guarantee that the transition relation can be viewed as a function in this manner.

So, maintain a HashMap<StateInput, State> trans and do trans.put(StateInput(q0, 1), q1) for the example you gave, where

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

回复收藏 0 原文

梦冥 2024-12-12 14:59:46

也许是这样的？

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

  // ...

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

  // ...
}

Something like this, maybe?

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

  // ...

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

  // ...
}

回复收藏 0 原文

~没有更多了~