Problem
In an effort to learn Java, I have written a simple DFA simulator, where a DFA is emulated using an object with a collection of states and inputs. Inputs can then be passed to the DFA to cause it to switch between the states according to a transition table. I hope to expand it with functions which can execute when a Transition occurs in the future.
I’m coming mainly from C#, so tips on how to write idiomatic Java would be appreciated.
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;
}
}
Usage example
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");
Solution
import java.security.InvalidParameterException;
I’m pretty sure that you actually wanted java.lang.IllegalArgumentException here 🙂 You do not need to explicitly import that, btw. Types from the java.lang package are automatically imported.
* Keys are of the form input,currentState.
That is somewhat unconventional. Especially given that you claim to implement a deterministic automaton, it would make significantly more sense to look up by state and then by input.
That should also be accomplishable in constant time (two pointer dereferencings), and not require building a String input + "," + currentState.
In addition it’s much less prone to errors when the inputAlphabet or your states can contain the separator char. Consider:
inputAlphabet = new String[] { "foo,bar", "foo", "bar" };
states = new String[] { "bar", "bar,bar", "foo" };
which is “foo,bar,bar” now? is it "foo" + "," + "bar,bar" or "foo,bar" + "," + "bar"?
I now see that you do actually check for that in your constructor explicitly. It’s good that you found the problem, the solution could use some work though 🙂
private final HashMap<String, Transition> transitions = new HashMap<>();
I really like that you’ve declared your fields final wherever possible.
I also like the use of the diamond operator.
As opposed to C#, Java interfaces are not explicitly prefixed with I. It is still preferred to use interfaces for members. Accordingly this should be:
private final Map<String, Transition> transitions = new HashMap<>();
Which reminds me… you should use private final Map<String, List<Transition>>, that simplifies the lookup by cutting out the key-aggregation. It additionally better reflects what a DFA really works like.
It also allows you to use a bit more modern features in 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;
}
Last but not least: I get that going to Java makes one miss C#’s Properties, but this is not an acceptable coding style in Java.
I can warmly recommend using Project Lombok to take care of autogenerating getters (and if needed setters) for your data holder classes.