Как конвертировать NFA / DFA в Java?

Question

У меня есть сценарий, в котором я разработал NFA и, используя JFLAP, преобразовал его в DFA.

Мне нужно знать, как его кодировать на Java?

В основном, как реализовать эти переходы состояний в Java. Я видел несколько примеров, которые делают это с помощью операторов switch и if, но я не вижу никакого отношения к дизайну DFA / NFA и как использовать его для реализации в Java.

Answer 1

, если вы хотите использовать более объектно-ориентированный дизайн, в то время как (true) switch (состояние) {...}

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 содержит реализацию DFA / NFA (конечных автоматов) с алфавитом Unicode (UTF16) и поддержкой стандартных операций регулярного выражения (конкатенация, объединение, звезда Клини) и ряд нестандартных операций (пересечение , дополнения и пр.)

Answer 3

Хотя вы бы уже реализовали это, но есть очень хорошая реализация, которую легко переварить. Используйте Digraph для поддержки переходов epsilon и стека для отслеживания выражений. Проверьте эту ссылку от RS NFA.java .