Automaton Implementation in Java

This post will address the problem of implementing finite states machines into java. If you don’t know what FSM are or where can be used you may be keen on reading this, this and this.

If you ever found yourself in the situation of using a FSM on your design you have probably started to write classes for every state which implemented the same interface. A good design might have been:

interface State { }
class State_1 implements State {}
class State_2 implements State {}
...

And you probably had a class that managed these states and the transitions between them, and another that implemented the Context of the FSM (the input band strip) and another interface for the starting states and one more for the end states and so forth. A lot of classes spread out in a lot of files that makes you to quickly lose track of them.

There is another way: using enums.

Enums are essentially list of classes, and each member of the enum may have a different implementation. suppose we have the following state machine that we want to implement:

Init -('a')-> A
Init -(else)-> Fail
A -('b')-> B
A -('c')-> C
A -('a')-> A
A -('')-> End
A -(else)-> Fail
B -('c')-> C
B -('b')-> B
B -('')-> End
B -(else)-> Fail
C -('c')-> C
C -('')-> End
C -(else)-> Fail

This FSM will validate the following regexp: ^(a+)(b*)(c*)$. We can write the states as elements of the enum State as follows:

interface State {
    public State next();
}

class Input {
    private String input;
    private int current;
    public Input(String input) {this.input = input;}
    char read() { return input.charAt(current++); }
}
 
enum States implements State {
    Init {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'a': return A;
                default: return Fail;
            }
        }
    },
    A {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'a': return A;
                case 'b': return B;
                case 'c': return C;
                case '': return null;
                default: return Fail;
            }
        }
    },
    B {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'b': return B;
                case 'c': return C;
                case '': return null;
                default: return Fail;
            }
        }
    },
    C {
        @Override
        public State next(Input word) {
            switch(word.read()) {
                case 'c': return C;
                case '': return null;
                default: return Fail;
            }
        }
    },
    Fail {
        @Override
        public State next(Input word) {
               return Fail;
        }
    };
 
    public abstract State next(Input word);
}

What we’ve done is we’ve defined the transitions of every state inside each enum. Each transition returns a new state and as such we can cycle through them more efficiently:

State s;
Input in = new Input("aabbbc");
for(s = States.Init; s != null || s != States.Fail; s = s.next(in)) {}
 
if(s == null) {System.out.printlin("Valid!");}
else {System.out.println("Failed");}

At this point, we have either validated the string or failed. It is a simple and elegant design.

We could further improve the implementation by separating the final states from the main ones as to simplify the exit condition of the traversal. We will define another interface called FinalState and a second enum that would contain the desired exit states (changing also the States enum accordingly):

interface FinalState extends State {}
enum FinalStates implements FinalState {
    Fail {
        @Override
        public State next(Input word) {
               return Fail;
        }
    },
    Ok {
        @Override
        public State next(Input word) {
               return End;
        }
    }
}

As such, the traversal will be somewhat simplified:

for(s = States.Init; !(s instanceof FinalState); s = s.next(in)) {}
switch(s) {
    case Fail: System.out.printlin("Valid!"); break;
    case Ok: System.out.println("Failed"); break;
    default: System.out.println("Undefined"); break;
}

The advantage is that (besides a simpler traversal) we could specify more than two final states. Most of the times, a FSM will have more than one exit point so this last improvement is recommended for the long-term. You can also place all these enums and interfaces inside the same source file and have the whole logic in one place rather than surf through multiple tabs in order to understand how the flow works.

As a conclusion, using enums makes for a more compact and meaningful implementation of a FSM. You have all the logic in one file and all traversal is painless. You will also have a much more easier debugging experience since the name of the states in which you’ve translated will appear in the debugger ( the variable s will change its value accordingly, bearing the name of the new state) rather have to figure out what class you have just jumped to. All in all I think it’s a good technique to have in mind.