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

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

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

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

Источник

3 ответа

Решение

Если вы хотите использовать более объектно-ориентированный дизайн, в то время как (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
}
Источник

Взгляни на dk.brics.automaton:

Этот пакет Java содержит реализацию DFA/NFA (конечных автоматов) с алфавитом Unicode (UTF16) и поддержкой стандартных операций с регулярными выражениями (конкатенация, объединение, звезда Клини) и ряд нестандартных операций (пересечение, дополнение, так далее.)

Источник

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

Источник
Другие вопросы по тегам