我是否可以为一个DFA状态转换使用Java的java.util.Set中
-
22-07-2019 - |
题
我实现DFA尽可能靠近我可以正式定义为一个学习锻炼(和博客材料)
我计划使用其中一组涉及在定义一个java.util.Set中。
定义包括一组元组来定义的法律状态转换:(状态,符号) - > nextState
我有成员的状态,符号和nextState过渡分类。我已经实现equals()和hashCode()方法来表示两个转变是相等的,如果他们匹配状态和符号。然后,我有过渡实例的java.util.Set中。
在我的处理算法,我的当前状态,当我读下一个符号。我预计使用这两个拔出从集,然后这会告诉我的下一个状态的匹配过渡建设转变对象,我可以遍历。
可是 - 我没有看到提取用于进一步使用java.util.Set中的成员的任何方式。我可以删除(对象O),但只是返回布尔。
我在做什么错了?
解决方案
设置可能不是你想用这个东西。我的建议是使用一个List <过渡>,也可能是地图<国家,名单<转型>>。我不知道这将是更好的,而无需实际构建它,做一些基准测试。
其他提示
这听起来好像你平等的压倒一切的()和hashCode()是可疑的,因为原来的过渡相匹配的一个中根据等于(下集),但两者不能互换(否则你只是将使用新过渡以代替原始的。)
您可能需要一个类,只不过是一个没有其他属性状态和符号的组合,并使用它作为一个地图的关键。或者,也可以使用一个Map<State, Map<Symbol, State>>
我与马修布鲁贝克同意Set
可能不是你所需要的。你可能会想尝试enums
代替;请参阅爪哇词汇一个例子。
你能不能做到这一点,而无需国家的一些外部收集,甚至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作为参数,并如果它匹配,则返回真或假),并且如果标准匹配时,它会向状态指出过由过渡移动的状态的指针。
中的代码可能看起来像部份
public void move(int input){
for(transition t : currentState.transitions){
if(t.getCriteria().matches(input)){
currentState = t.getNextState();
break;
}
}
}
如果你只是想实现一个模式匹配引擎,因为图案是不太可能改变一个国家的设计模式可能是不必要的。乍得所指出的,使用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*)
描述的正则语言”,即一个‘a’后跟一个的两个多重或三个多倍数‘b’的第