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 Video Library
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
View Events Video Library
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
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

Integrating PostgreSQL Databases with ANF: Join this workshop to learn how to create a PostgreSQL server using Instaclustr’s managed service

Mobile Database Essentials: Assess data needs, storage requirements, and more when leveraging databases for cloud and edge applications.

Monitoring and Observability for LLMs: Datadog and Google Cloud discuss how to achieve optimal AI model performance.

Automated Testing: The latest on architecture, TDD, and the benefits of AI and low-code tools.

Related

  • Effective Java Collection Framework: Best Practices and Tips
  • Generics in Java and Their Implementation
  • Bridge Design Pattern in Java: An Intro, Real-time Examples, Class/Seq Diagram, and Implementation
  • Adapter Design Pattern in Java [Language Translator] - Introduction, Example, and Implementation

Trending

  • Designing Databases for Distributed Systems
  • How to Submit a Post to DZone
  • Demystifying Project Loom: A Guide to Lightweight Threads in Java
  • Agile Estimation: Techniques and Tips for Success
  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.40K 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.

Related

  • Effective Java Collection Framework: Best Practices and Tips
  • Generics in Java and Their Implementation
  • Bridge Design Pattern in Java: An Intro, Real-time Examples, Class/Seq Diagram, and Implementation
  • Adapter Design Pattern in Java [Language Translator] - Introduction, Example, and Implementation

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

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: