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("Failed"); break;
    case Ok: System.out.println("Valid!"); 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.

Reference: Automaton implementation in Java from our JCG partner Attila-Mihaly Balazs at the Transylvania JUG blog.

Related Whitepaper:

Bulletproof Java Code: A Practical Strategy for Developing Functional, Reliable, and Secure Java Code

Use Java? If you do, you know that Java software can be used to drive application logic of Web services or Web applications. Perhaps you use it for desktop applications? Or, embedded devices? Whatever your use of Java code, functional errors are the enemy!

To combat this enemy, your team might already perform functional testing. Even so, you're taking significant risks if you have not yet implemented a comprehensive team-wide quality management strategy. Such a strategy alleviates reliability, security, and performance problems to ensure that your code is free of functionality errors.Read this article to learn about this simple four-step strategy that is proven to make Java code more reliable, more secure, and easier to maintain.

Get it Now!  

Leave a Reply


+ five = 13



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.

Sign up for our Newsletter

20,709 insiders are already enjoying weekly updates and complimentary whitepapers! Join them now to gain exclusive access to the latest news in the Java world, as well as insights about Android, Scala, Groovy and other related technologies.

As an extra bonus, by joining you will get our brand new e-books, published by Java Code Geeks and their JCG partners for your reading pleasure! Enter your info and stay on top of things,

  • Fresh trends
  • Cases and examples
  • Research and insights
  • Two complimentary e-books