java - 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

あなたは今までにそれを実装したでしょうが、消化しやすい非常に優れた実装があります. Digraph を使用してイプシロン遷移とスタックを維持し、式を追跡します。RS NFA.javaからこのリンクをチェックしてください。