如何将 NFA/DFA 转换为 java?

Question

我有一个场景，我设计了 NFA 并使用 JFLAP 将其转换为 DFA。

我需要知道如何用Java编写它？

基本上如何在 Java 中实现这些状态转换。我见过一些使用 switch 和 if 语句执行此操作的示例，但我看不到与 DFA/NFA 设计以及如何使用它在 Java 中实现的任何关系。

Answer 1

如果您想在 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
}

Answer 2

看一下 dk.brics.automaton：

此 Java 包包含使用 Unicode 字母表 (UTF16) 的 DFA/NFA（有限状态自动机）实现，并支持标准正则表达式操作（串联、并集、Kleene 星形）和许多非标准操作（交集） 、补码等）

Answer 3

虽然你现在已经实现了它，但是有一个非常好的实现，很容易理解。使用有向图来维护 epsilon 转换并使用堆栈来跟踪表达式。查看来自 RS NFA.java 的链接。