DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
  1. DZone
  2. Coding
  3. Java
  4. Automaton Implementation in Java

Automaton Implementation in Java

Cristian  Lungu user avatar by
Cristian Lungu
·
Mar. 15, 12 · Interview
Like (0)
Save
Tweet
Share
15.30K Views

Join the DZone community and get the full member experience.

Join For Free

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.

Implementation Java (programming language) Automaton

Published at DZone with permission of Cristian Lungu, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • AWS CodeCommit and GitKraken Basics: Essential Skills for Every Developer
  • Simulating and Troubleshooting BLOCKED Threads in Kotlin [Video]
  • Low-Code Development: The Future of Software Development
  • Accelerating Enterprise Software Delivery Through Automated Release Processes in Scaled Agile Framework (SAFe)

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: