我可以使用java.util.Set中

Question

我实现DFA接近实现了DFA态跃迁Java作为我可以正式定义为一个学习锻炼（和博客材料）

我计划使用定义中涉及集合的java.util.Set。

该定义涉及到一组元组来定义合法的状态转换：（state，symbol） - > nextState。

我有一个Transition成员状态，符号和nextState类。我已经实现了equals（）和hashCode（）来表示如果它们在状态和符号上匹配，那么两个Transitions是相等的。然后我有一个java.util.Set Transition实例。

在我的处理算法中，当我读取下一个符号时，我有当前状态。我期望使用这两个构建一个Transition对象来从Set中取出匹配的Transition，然后告诉我下一个状态，并且我可以迭代。

但是 - 我没有看到任何提取java.util.Set成员的方式以供进一步使用。我可以删除（Object o），但只是返回布尔值。

我在做什么错？

Answer 1

设置可能不是你想要用于这个。我的建议是使用列表< Transition>，或可能使用Map < State，列表< Transition >>。我不确定没有真正建立它并做一些基准测试，哪个更好。

Answer 2

这听起来好像你的equals（）和hashCode（）的覆盖是可疑的，因为原始转换匹配equals（）中的集合中的一个，但两者不可互换（否则你只需使用新的过渡代替原来的）。

你可能想要一个类，它只是状态和符号的组合，没有其他属性，并将它用作Map中的一个键。或者你可以使用Map<State, Map<Symbol, State>>

Answer 3

我同意马修布鲁贝克认为Set可能不是你所需要的。您可能想尝试使用enums;例如，请参阅Java Glossary。

Answer 4

如果没有外部状态的集合，甚至是Transistion对象，你难道不能完成这个吗？如果State类的定义如下：

public class State 
{ 
    private Map<Symbol, State> transitions = new HashMap<Symbol, State>(); 

    public State() { /* populate transitions somehow */ } 

    public State nextState(Symbol symbol) { return transitions.get(symbol); } 
} 

然后，如果你有到初始状态的参考，你可以从状态移动到状态是这样的：

State initial = getInitialStateSomehow(); 
State second = initial.nextState(SYMBOL_1); 
State third = initial.nextState(SYMBOL_2); // etc... 

Answer 5

是的，我是那种对为什么甚至需要一个集合感到困惑。

对于一个简单的状态机，你可以只使用静态整数和一个case语句做你的状态机这样的：

int STATE1 = 1; 
int STATE2 = 2; 
int STATE3 = 3; 
int STATE4 = 4; 

int currentstate = STATE1 ; 
int input = nextInput(); 


while(currentstate != STATE4){ 
    switch(input){ 
     case STATE1: 
      if(input == 'a') currentstate = STATE2; 
      break; 
     case STATE2: 
      if(input == 'b') currentstate = STATE3; 
      else currentstate = STATE1; 
      break; 
     case STATE3: 
      if(input == 'c') currentstate = STATE4; 
      else currentstate = STATE1; 
     } 
} 

这是一个基本的状态机，将查找包含“ABC”的任意字符串。你可以很容易地扩展它，寻找ab * c或任何你想要的。

那么，如果你想要一个运行时建立的动态状态机呢？好吧，我也是这样做的。这并不难。我所做的是创建一个带有转换列表的状态类。每个转换都有一个指向下一个状态的指针以及链接的标准。

因此，例如，STATE1将具有标准“a”和指向表示STATE2的某个对象的指针的转换。代码看起来会检查条件（这可能是一个将int作为参数的对象，如果匹配则返回true或false），并且如果条件匹配，则会将状态指针移动到过渡指向的状态。

的代码可能看起来像部份

public void move(int input){ 
    for(transition t : currentState.transitions){ 
     if(t.getCriteria().matches(input)){ 
     currentState = t.getNextState(); 
     break; 
     } 
    } 
} 

Answer 6

如果你只是想实现一个模式匹配引擎，状态设计模式可能会因为图案是不可能改变的是不必要的。正如Chad指出的那样，在这种情况下，使用switch来编码转换函数是完全可以接受的。

下面是一个使用设置的非确定性模式匹配自动机的示例：

public boolean validate() { 
    Set<Integer> currentStates = new HashSet<Integer>(); 
    final Set<Integer> acceptingStates = new HashSet<Integer>(); 

    currentStates.add(0); // Initial state. 
    acceptingStates.add(1); 
    acceptingStates.add(3); 
    acceptingStates.add(6); 

    for (int i = 0; i < getInput().length(); i++) { 
     char c = getInput().charAt(i); 
     Set<Integer> newStates = new HashSet<Integer>(); 

     for (int state : currentStates) { 
      switch (state) { 
       case 0: 
        if (c == 'a') 
         newStates.add(1); 
        break; 
       case 1: 
        if (c == 'b') { 
         newStates.add(2); 
         newStates.add(4); 
        } 
        break; 
       case 2: 
        if (c == 'b') 
         newStates.add(3); 
        break; 
       case 3: 
        if (c == 'b') 
         newStates.add(2); 
        break; 
       case 4: 
        if (c == 'b') 
         newStates.add(5); 
        break; 
       case 5: 
        if (c == 'b') 
         newStates.add(6); 
        break; 
       case 6: 
        if (c == 'b') 
         newStates.add(4); 
        break; 
      } 
     } 

     if (newStates.size() == 0) 
      return false; 
     currentStates = newStates; 

     System.out.printf("Character read: %c\n", c); 
     System.out.printf("Current states: "); 
     printStates(currentStates); 
    } 

    for (int state : acceptingStates) 
     if (currentStates.contains(state)) 
      return true; 
    return false; 
} 

此自动机识别由图案"a(bb*|bbb*)描述的正则语言的输入字”，即，‘一’，接着为无论多两个或三个“b”的倍数