DFA Introduction

A Deterministic Finite Automaton (DFA) is a state diagram with some additional structure. Before jumping in the code some definitions are necessary:

An Alphabet is a finite set of symbols. A symbol can be anything from a number to a rune, to a complex Java object.

A word or string in an alphabet A is a finite sequence of symbols of A.

Let A be an alphabet and S be a finite set of states.
A State Transition Diagram is just a function mapping a symbol and a state to a state:

delta: AxS --> S

A DFA consists of such a State Transition Diagram together with an initial state s0 in S, and a non-empty set of final states also in S.

So what's all this about? Finite Automata are all about recognizing languages over alphabets, where a language is simply a subset on the set of all words. In particular, FAs can recognize regular expressions.
It works as follows: You feed the DFA a string which is a sequence of symbols. The DFA sets itself in motion by starting at the initial state and following the transition diagram based on the set of symbols. If when symbols are accounted for, the DFA ends in one of the termination states, then it is a valid word. If not, then it is an invalid word.

Let's make all this concrete with an example.
Let A be the alphabet of two symbols A = {0,1}.
We are going to build an FSA that recognizes the language that accepts all strings with an odd number of 1s. This is a simple machine with only two states. The DFA implementation here uses an abstract builder pattern:

DFABuilder<String, Character> builder = DFA.newDFA(alphabet);
builder.setInitialState("A").
        addFinalState("B").
        addTransition("A", "A", '0').
        addTransition("A", "B", '1').
        addTransition("B", "A", '1').
        addTransition("B", "B", '0');
DeterministicFiniteAutomaton<String, Character> machine = builder.build();

If when calling "build" the automaton is not complete, the builder is going to throw a DFABuilderException.

Now let's test out the automaton with some JUnite assert statements:

assertTrue(machine.accepts(BasicWord.fromString("1011")));
assertTrue(machine.accepts(BasicWord.fromString("0010000011000101")));
assertFalse(machine.accepts(BasicWord.fromString("1111")));
assertFalse(machine.accepts(BasicWord.fromString("1010101")));