Deterministic finite automaton in Java

Question

Formally, a deterministic finite automaton is a 5-tuple \$M = (Q, \Sigma, \delta, q_0, F)\$, where

• \$Q\$ is the set of all possible states
• \$\Sigma\$ is the alphabet
• \$\delta \colon Q \times \Sigma \to Q\$ is the transition function
• \$q_0\$ is the starting state
• \$F\$ is the set of accepting states

Basically, each DFA represents a so-called regular language \$L\$, and given input string \$s\$, answers whether \$s \in L\$. This is done in \$\mathcal{O}(|s|)\$ time simply by consuming each character and making the state transitions starting from \$q_0\$; if after reading the entire string we end up in a state in \$F\$, the DFA accepts the string.

Please, tell me anything that comes to mind.

TransitionFunction.java

package net.coderodde.dfa;

import java.util.HashMap;
import java.util.Map;

/**
 * This class implements a transition function.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 2, 2016)
 */
public class TransitionFunction {

    private final Map<Integer, Map<Character, Integer>> function = 
          new HashMap<>();

    public void setTransition(Integer startState, 
                              Integer goalState,
                              char character) {
        function.putIfAbsent(startState, new HashMap<>());
        function.get(startState).put(character, goalState);
    }

    public Integer process(Integer startState, char character) {
        if (!function.containsKey(startState)) {
            return null;
        }

        return function.get(startState).get(character);
    }
}

DFA.java

package net.coderodde.dfa;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;

/**
 * This class implements a 
 * <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton">
 * deterministic finite automaton</a>.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 2, 2016)
 */
public class DFA {

    private final TransitionFunction transitionFunction;
    private final int startState;
    private final Set<Integer> acceptingStates;

    public DFA(TransitionFunction transitionFunction,
               int startState,
               Set<Integer> acceptingStates) {
        this.transitionFunction = 
                Objects.requireNonNull(transitionFunction,
                                       "Transition function is null.");
        this.startState = startState;
        this.acceptingStates = 
                Objects.requireNonNull(acceptingStates,
                                       "Accepting state set is null.");
    }

    public boolean matches(String text) {
        Integer currentState = startState;

        for (char c : text.toCharArray()) {
            currentState = transitionFunction.process(currentState, c);

            if (currentState == null) {
                return false;
            }
        }

        return acceptingStates.contains(currentState);
    }

    public static void main(String[] args) {
        // A regular language over binary strings with even number of 1's.
        TransitionFunction transitionFunction = new TransitionFunction();

        transitionFunction.setTransition(0, 0, '0');
        transitionFunction.setTransition(1, 1, '0');
        transitionFunction.setTransition(0, 1, '1');
        transitionFunction.setTransition(1, 0, '1');

        Set<Integer> acceptingStates = new HashSet<>(Arrays.asList(0));
        DFA dfa = new DFA(transitionFunction, 0, acceptingStates);

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();

            if (line.trim().equals("end")) {
                break;
            }

            System.out.println(dfa.matches(line));
        }
    }
}

Answer 1

Java 8 constructs

The following

function.putIfAbsent(startState, new HashMap<>());
function.get(startState).put(character, goalState);

can be simplified by using the computeIfAbsent(key, mappingFunction) method. This method will return the current value associated with the given key or compute a new value for that key and return it. As such, you could have:

function.computeIfAbsent(startState, k -> new HashMap<>()).put(character, goalState);

Also, the following

if (!function.containsKey(startState)) {
    return null;
}
return function.get(startState).get(character);

can be also written more simply with the getOrDefault(key, defaultValue) method. This will return the value associated with the given key or else return the default value. You could have:

return function.getOrDefault(startState, Collections.emptyMap()).get(character);

When the map doesn't contain the key startState, an empty map (that was already instantiated, it is a cached value) is returned with Collections.emptyMap().

Code structure

You currently have a class TransitionFunction that holds all transitions and offers a method to go from one state to another for a particular character.

I find the name TransitionFunction a bit misleading because it would imply that the class is in fact a Function in that it is a functional interface taking a parameter and returing a value. But it is more than that since it is the class that holds all possible transitions.

Why not rename the class Transitions and:

• Rename the method setTransition to addTransition to better reflect the fact that this method adds a transition (instead of setting it).
• Move the code for processing all transitions, that is currently placed inside the matches method, in this class. This method would be called processAll(Integer startState, char[] characters) and would process all the characters given starting at the given state.

This is what the class could look like

public class Transitions {

    private final Map<Integer, Map<Character, Integer>> function = new HashMap<>();

    public void addTransition(Integer startState, Integer goalState, char character) {
        function.computeIfAbsent(startState, k -> new HashMap<>()).put(character, goalState);
    }

    public Integer process(Integer startState, char character) {
        return function.getOrDefault(startState, Collections.emptyMap()).get(character);
    }

    public Integer processAll(Integer startState, char[] characters) {
        return IntStream.range(0, characters.length)
                        .boxed()
                        .reduce(startState, (s, i) -> s == null ? null : process(s, characters[i]));
    }

}

Notice that the processAll method leverages an IntStream over the indexes of the input array. The final state is calculating by reducing from the starting state and calling process each time on the accumulated result. The difference between your initial code is that it is not short-circuiting; if you wish to keep that, you can keep your for loop as-is.

With this change, the matches method would just be:

public boolean matches(String text) {
    Integer finalState = transitionFunction.processAll(startState, text.toCharArray());
    return finalState != null && acceptingStates.contains(finalState);
}

Using Optional

You are currently relying on null values to mean "no state". Using an Optional would remove all that. We could make the methods process and processAll return an Optional<Integer> with

public Optional<Integer> process(Integer startState, char character) {
    return Optional.ofNullable(function.getOrDefault(startState, Collections.emptyMap()).get(character));
}

public Optional<Integer> processAll(Integer startState, char[] characters) {
    return IntStream.range(0, characters.length)
                    .boxed()
                    .reduce(
                      Optional.of(startState),
                      (o, i) -> o.flatMap(s -> process(s, characters[i])),
                      (o1, o2) -> o1.map(Optional::of).orElse(o2)
                    );
}

process makes a call to Optional.ofNullable to wrap the value. The reducing part works on the optional values. The combiners combines two optional into a single one.

Then, the matches method becomes

public boolean matches(String text) {
    return transitionFunction.processAll(startState, text.toCharArray())
                             .map(acceptingStates::contains)
                             .orElse(false);
}