我正在实施一个尽可能接近正式定义的 DFA 作为学习练习（和博客材料）
我计划使用一个 java.util.Set ，其中定义中涉及一个集合。
该定义涉及一组元组来定义合法的状态转换：(state,symbol) -> nextState。
我有一个带有成员 state、symbol 和 nextState 的 Transition 类。我已经实现了 equals() 和 hashCode() 来指示如果两个转换在状态和符号上匹配，则它们是相等的。然后我有一个 java.util.Set 的 Transition 实例。
在我的处理算法中，当我读取下一个符号时，我拥有当前状态。我预计使用这两个构建一个 Transition 对象，从 Set 中提取匹配的 Transition，然后它会告诉我下一个状态，我可以迭代。
但是 - 我看不到任何提取 java.util.Set 成员以供进一步使用的方法。我可以删除（对象 o），但这只是返回布尔值。
我究竟做错了什么？
Set 可能不是您想要使用的。我的建议是使用 List<Transition>，或者可能是 Map<State,List<Transition>>。如果不实际构建它并进行一些基准测试，我不确定哪个会更好。
听起来好像您对 equals() 和 hashCode() 的覆盖是可疑的，因为原始转换根据 equals() 与集合中的转换匹配，但两者不可互换（否则您只需使用新转换到位原来的。）
您可能想要一个只是状态和符号组合而没有其他属性的类，并将其用作 Map 中的键。或者，您可以使用Map<State, Map<Symbol, State>>
我同意 Matthew Brubaker 的观点，这Set可能不是您所需要的。您可能想尝试一下enums；有关示例，请参见Java 词汇表。
如果没有一些外部状态集合，甚至是 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...
是的，我有点困惑为什么甚至需要一个集合。
对于一个简单的状态机，您可以使用静态整数和 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;
}
}
}
如果您只想实现模式匹配引擎，则可能不需要状态设计模式，因为模式不太可能改变。正如 Chad 所指出的，switch在这种情况下，使用 a 对转换函数进行编码是完全可以接受的。
这是一个使用集合的非确定性模式匹配自动机的示例：
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*)“”描述的常规语言的输入词，即“a”后跟两个的倍数或三个许多“b”的倍数。