What is a state machine in Java


Automata are not only an important tool in theoretical computer science in the field of formal languages ​​for checking language affiliations. A derived application is the pattern recognition in character strings with the help of regular expressions. But also many protocols of distributed systems (e.g. TCP) take up the concept of state machines in order to react differently to events depending on different internal states. Of course, these state machines must also be mapped in software when implementing protocols. In this article I would like to use a simple DFA to show how such state machines can be implemented in Java using the state pattern.

In this example a DFA is to be constructed that accepts exactly those from all possible character strings consisting of ones and zeros in which the partial words 01 and 10 occur equally often. The graph on the right shows how the machine works. In addition to the start state (S), there are two valid end states (A, X) with the same number of occurrences, as well as two states (B, Y) that do not represent a valid end state.

If you want to implement such a construction, you have to map states, transitions and valid combinations. The state pattern of the GoF as a behavior pattern is suitable for object-oriented languages, since it is clearer, cleaner and more expandable than cascades of If queries or switch statement constructs. The basic idea here is to outsource states with the associated transitions to their own objects and to transfer the relevant reference to its current state to the object with the state. This stateful object then delegates changes to its current state object, which may be replaced after the transition. In Java, it makes sense to implement the states as enum instances and to let them implement an interface that defines the transitions. In addition, the states, i.e. enum instances, can be queried as to whether they represent a valid final state.
The automaton class now represents the actual object, which is stateful, but with outsourced handling of the states:

Transitions.java - List of transitions as an interface

/ ** * Interface listing possible transitions to be implemented by states * / public interface Transitions {public void readZero (Automaton a); public void readOne (automaton a); }

State.java - States as enum types

/ ** * Enum type for states * / public enum State implements Transitions {/ ** * Initial State - S * / S {@Override public void readOne (Automaton a) {a.setState (X); } @Override public void readZero (Automaton a) {a.setState (A); } @Override public boolean isFinal () {return true; }}, / ** * Final State - A * / A {@Override public void readOne (Automaton a) {a.setState (B); } @Override public void readZero (Automaton a) {a.setState (A); } @Override public boolean isFinal () {return true; }}, / ** * State -B * / B {@Override public void readOne (Automaton a) {a.setState (B); } @Override public void readZero (Automaton a) {a.setState (A); } @Override public boolean isFinal () {return false; }}, / ** * Final State - X * / X {@Override public void readOne (Automaton a) {a.setState (X); } @Override public void readZero (Automaton a) {a.setState (Y); } @Override public boolean isFinal () {return true; }}, / ** * State -Y * / Y {@Override public void readOne (Automaton a) {a.setState (X); } @Override public void readZero (Automaton a) {a.setState (Y); } @Override public boolean isFinal () {return false; }}; / ** * Is state final? * @return true if final * / abstract public boolean isFinal (); }

Automaton.java - The stateful object including the test in the main method.

/ ** * Automaton class * / public class Automaton {// Initial state private State state = State.S; public void setState (State s) {this.state = s; } public void readZero () {// Delegate ... state.readZero (this); } public void readOne () {// Delegate ... state.readOne (this); } public boolean isInFinalState () {// Delegate ... return state.isFinal (); } public static void main (String [] args) {Automaton a = new Automaton (); String s1 = "11010101"; for (char c: s1.toCharArray ()) {switch (c) {case '1': a.readOne (); break; case '0': a.readZero (); break; }} System.out.println (a.isInFinalState ()); // true ...}}

I have chosen this sample program with a DFA to make it easier to understand; of course, much more complex processes can be modeled with this pattern. For example, the machine could be a book object in a library and the transitions could be actions such as borrowing, extending or returning the book. The states as enum types would then also contain more business logic than simply changing the state as in this example.

Original article: State machine in Java using the state pattern

Category: java

Tags: design patterns, java

These icons link to bookmark services where users can find new content and share it with others.