我有一个场景,我设计了 NFA 并使用 JFLAP 将其转换为 DFA。
我需要知道,如何用 Java 编写代码?
基本上如何在 Java 中实现这些状态转换。我已经看到了一些使用 switch 和 if 语句执行此操作的示例,但我看不到与 DFA/NFA 设计以及如何使用它在 Java 中实现的任何关系。
我有一个场景,我设计了 NFA 并使用 JFLAP 将其转换为 DFA。
我需要知道,如何用 Java 编写代码?
基本上如何在 Java 中实现这些状态转换。我已经看到了一些使用 switch 和 if 语句执行此操作的示例,但我看不到与 DFA/NFA 设计以及如何使用它在 Java 中实现的任何关系。
如果你想使用更面向对象的设计而不是 while(true)switch(state){...}
public class State{
private Map<Character,State> transitions=new HashMap<Character,State>();
public void addTransition(char ch,State st){
transitions.put(ch,st);
}
public State next(char ch){
return transitions.get(ch);
}
private boolean fin=false;
public boolean isFinal(){return fin;}
public boolean setFinal(boolean f){fin=f;}
}
然后循环将是
State currState=startState;
while(currState!=null && input.hasNextChar()){//you can also end directly when final state is reached
char next = input.nextChar();//get next character
currState = currState.next(next);
}
if(currState!=null && currState.isFinal()){
// reached final state
}else{
// to bad didn't match
}
这个 Java 包包含一个带有 Unicode 字母 (UTF16) 的 DFA/NFA(有限状态自动机)实现,并支持标准的正则表达式操作(连接、联合、Kleene 星)和一些非标准的操作(交集、补码、 ETC。)
虽然你现在已经实现了它,但是有很好的实现,很容易消化。使用 Digraph 来维护 epsilon 转换并使用堆栈来跟踪表达式。从 RS NFA.java查看此链接。