Простой симулятор ДКА в Java


В стремлении изучать Java, я написал простой симулятор АР, где АР эмулируется с помощью объекта с коллекцией состояний и входов. Входов может быть передан в МИД, чтобы заставить его переключиться между государствами в соответствии с таблицей переходов / выходов. Я надеюсь, чтобы расширить его функции, которые можно выполнять при Transition происходит в будущем.

Я иду в основном из C#, так что советы о том, как писать идиоматические Ява будут оценены.

DeterministicFiniteAutomaton.java

import java.util.List;
import java.util.stream.Stream;
import java.security.InvalidParameterException;
import java.util.Arrays;
import java.util.HashMap;

/**
 * Represents a deterministic finite automaton (DFA), with a set of states and
 * transitions between those states.
 */
public class DeterministicFiniteAutomaton {
    private final String[] states;
    private final String[] inputAlphabet;
    private final String[] acceptingStates;

    /**
     * A HashMap of transitions. A HashMap is used to speed up searching
     * through the table to find the correct transition.
     * Keys are of the form input,currentState.
     */
    private final HashMap<String, Transition> transitions = new HashMap<>();

    private String startState;
    private String currentState;

    /**
     * Constructs a new DFA.
     * 
     * @param states The set of states which the DFA may be in.
     * @param inputAlphabet The set of inputs which may be supplied to the DFA.
     * @param acceptingStates The subset of states which are accepting.
     * @param transitions A list of transitions between states on inputs.
     * @param startState The starting state.
     */
    public DeterministicFiniteAutomaton(String[] states, String[] inputAlphabet,
        String[] acceptingStates, Transition[] transitions, String startState) {
        // Due to transition keys' comma-separated nature, state or input names 
        // may not contain commas

        if (Stream.of(states).anyMatch(x -> x.contains(","))) {
            throw new InvalidParameterException
                ("State names may not contain commas");
        }

        if (Stream.of(inputAlphabet).anyMatch(x -> x.contains(","))) {
            throw new InvalidParameterException
                ("Inputs may not contain commas");
        }

        this.states = states;
        this.inputAlphabet = inputAlphabet;
        this.acceptingStates = acceptingStates;

        this.startState = startState;
        this.currentState = startState;

        for (Transition t : transitions) {
            List<String> statesAsList = Arrays.asList(this.states);
            if (!statesAsList.contains(t.newState)
                || !statesAsList.contains(t.startState)) {
                throw new InvalidParameterException
                    ("Transition refers to state which does not exist");
            }

            if (!Arrays.asList(inputAlphabet).contains(t.input)) {
                throw new InvalidParameterException
                    ("Transition refers to input which does not exist");
            }

            String key = getKeyForTransition(t.input, t.startState);

            this.transitions.put(key, t);   
        }     
    }

    /**
     * Resets the DFA to its starting state.
     * This method returns the object it is called on, so may be chained.
     */
    public DeterministicFiniteAutomaton reset() {
        currentState = startState;
        return this;
    }

    /**
     * Given a valid input, transitions the DFA to another state according to
     * the transition table.
     * This method returns the object it is called on, so may be chained.
     * @param input The input to the DFA.
     */
    public DeterministicFiniteAutomaton input(String input) {
        // Check that this input is contained within the input alphabet
        if (!Arrays.asList(inputAlphabet).contains(input)) {
            throw new InvalidParameterException
                ("'" + input + "' is not a valid input");
        }

        String key = getKeyForTransition(input, currentState);

        Transition transition = transitions.get(key);
        if (transition == null) {
            throw new InvalidParameterException
                ("No transition found for: " + input);
        }

        currentState = transition.newState;

        return this;
    }

    /**
     * Returns the current state of the DFA.
     */
    public String getState() {
        return currentState;
    }

    /**
     * Returns true if the current state is contained within the set of
     * accepting states.
     */
    public boolean isAccepting() {
        return Arrays.asList(acceptingStates).contains(currentState);
    }

    /**
     * Calculates the HashMap key used to look up the transition which should
     * be taken, given the current state and an input.
     */
    private String getKeyForTransition(String input, String state) {
        return input + "," + state;
    }
}

Transition.java

/**
 * Represents a transition between two states based on an input.
 */
public class Transition {
    public final String startState;
    public final String input;
    public final String newState;

    /**
     * Constructs a new transition.
     * @param startState The state to start from.
     * @param input The input on which the transition should trigger.
     * @param newState The state to transition to.s
     */
    public Transition(String startState, String input, String newState) {
        this.startState = startState;
        this.input = input;
        this.newState = newState;
    }
}

Пример использования

DeterministicFiniteAutomaton turnstileDfa =
    new DeterministicFiniteAutomaton(
        new String[] { "Locked", "Unlocked" },
        new String[] { "Push", "Coin" },
        new String[] { "Locked" },
        new Transition[] {
            new Transition("Locked", "Push", "Locked"),
            new Transition("Locked", "Coin", "Unlocked"),
            new Transition("Unlocked", "Push", "Locked"),
            new Transition("Unlocked", "Coin", "Unlocked")
        },
        "Locked"
    );

turnstileDfa.input("Coin").input("Push");


786
2
задан 5 февраля 2018 в 01:02 Источник Поделиться
Комментарии
1 ответ


import java.security.InvalidParameterException;

Я уверен, что вы на самом деле хотели java.lang.IllegalArgumentException вот :) вам не нужно явно импортировать, кстати. Типы из java.lang пакет автоматически импортируется.


 * Keys are of the form input,currentState.

Это несколько нетрадиционно. Особенно учитывая, что вы утверждаете, для реализации детерминированного автомата, было бы значительно больше смысла смотреть на состояние, а затем на вход.
Это также должно быть выполнимой в постоянное время (два указателя dereferencings), и не требуют построения строки input + "," + currentState.
Кроме того, он гораздо менее склонен к ошибкам, когда inputAlphabet или states может содержать разделитель типа char. Рассмотрим:

inputAlphabet = new String[] { "foo,bar", "foo", "bar" };
states = new String[] { "bar", "bar,bar", "foo" };

что "фу,бар,бар" сейчас? это "foo" + "," + "bar,bar" или "foo,bar" + "," + "bar"?

Теперь я вижу, что вы на самом деле проверить, что в вашем явно конструктор. Это хорошо, что вы нашли проблему, решение может не работать :)


 private final HashMap<String, Transition> transitions = new HashMap<>();

Мне очень нравится, что вы заявили о своем Поля final везде, где это возможно.
Мне также нравится использовать оператора Алмаз.

В отличие от C#, Java-интерфейсы явно не с приставкой I. Он по-прежнему предпочитали использовать интерфейсы для членов. Соответственно это должно быть:

private final Map<String, Transition> transitions = new HashMap<>();

Что напоминает мне... вы должны использовать private final Map<String, List<Transition>>, это упрощает поиск по выпиливанию ключ-агрегации. Кроме того, он лучше отражает того, что DFA действительно работает.

Это также позволяет использовать более современные input:

public DeterministicFiniteAutomaton input(String input) {
// input-checks have been performed on transitions.
// if no transition matches, the input may not have been in the alphabet
currentState = transitions.getOrDefault(input, Collections.emptyList())
.stream()
.first(t -> t.input.equals(input))
.orElseThrow(() -> new IllegalArgumentException("no transition found for: " + input))
.newState;
return this;
}

Последнее, но не менее важное: я понимаю, что происходит с Java делает один промах в C#свойства, но это не приемлемый стиль кодирования в Java.

Я могу тепло рекомендовать, используя проект Lombok, чтобы заботиться о автогенераторный добытчики (и при необходимости сеттеры) для держателя данных классов.

2
ответ дан 5 февраля 2018 в 03:02 Источник Поделиться