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, and
• \$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. My Java implementation follows:

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)); } } } 

Please, tell me anything that comes to mind.