Finite State Machines - Part II
To illustrate one way of programming a Finite State Machine we're going to use the example of the Decimal Number Validation FSM from part I. The code that makes up the validation FSM is contained in the file DecimalNumberValidator.java which uses three utility classes:
DFANetwork,java - This is a base class for FSMs and can be extended to create any FSM - in this case we're extending it to create our decimal number validation FSM.
State.java - This class is where most of the computation that makes the FSM work goes on.
TokenSet.java - This class is used to represent a set of tokens (in this case characters) that can be treated in the same way by a state in a FSM. Although it is possible to add a transition rule for each and every token accepted by a state - using this class saves a lot of time when we wish a set of tokens to be treated the same way. In the decimal number validation FSM this will be used to group all numerical characters into one, easily manipulated, set.
The first piece of code in the DecimalNumberValidator class we should look at is the constructor - It starts by defining a set of states that will form the FSM:
Then defines a pair of token sets to make our life easier:
Now comes the part where we actually build the FSM. We add transition rules for each token (or token set) to each of the states where they are required (which we know by looking at the diagram in part I - being able to draw your FSM always helps with this bit). Please note that we do not include junk, or waste, states in this section as they are not required:
And that it!! Our FSM is now ready to be used. All we need to do to use it is create a new instance of the DecimalNumberValidator class and start it running (remembering to provide it with a string to test) - like so:
You can download the full source code for the DecimalNumberValidator and utility classes - online documentation for the utility classes is also available. The downloadable source code is more extensive than just that outlined here - but this discussion, the documentation and taking a look at the code for the DecimalNumberValidator class should be enough to prepare you for building your own Finite State Machines.
DFANetwork,java - This is a base class for FSMs and can be extended to create any FSM - in this case we're extending it to create our decimal number validation FSM.
State.java - This class is where most of the computation that makes the FSM work goes on.
TokenSet.java - This class is used to represent a set of tokens (in this case characters) that can be treated in the same way by a state in a FSM. Although it is possible to add a transition rule for each and every token accepted by a state - using this class saves a lot of time when we wish a set of tokens to be treated the same way. In the decimal number validation FSM this will be used to group all numerical characters into one, easily manipulated, set.
The first piece of code in the DecimalNumberValidator class we should look at is the constructor - It starts by defining a set of states that will form the FSM:
State q0 = new State("q0");
this.defineStartState(q0, "");
State q1 = new State("q1");
State q2 = new State("q2");
State q3 = new State("q3", State.GOAL_STATE);
State q4 = new State("q4");
Then defines a pair of token sets to make our life easier:
char[] digit = {'9', '8', '7', '6', '5', '4', '3', '2', '1', '0'};
TokenSet digitSet = new TokenSet("digit", digit);
char[] dec = {'.'};
TokenSet dpSet = new TokenSet("dp", dec);
Now comes the part where we actually build the FSM. We add transition rules for each token (or token set) to each of the states where they are required (which we know by looking at the diagram in part I - being able to draw your FSM always helps with this bit). Please note that we do not include junk, or waste, states in this section as they are not required:
q0.addRule(digitSet, q1);
q0.addRule('-', q4);
q0.addRule(dpSet, q2);
q1.addRule(digitSet, q1);
q1.addRule(dpSet, q2);
q2.addRule(digitSet, q3);
q3.addRule(digitSet, q3);
q4.addRule(digitSet, q1);
q4.addRule(dpSet, q2);
And that it!! Our FSM is now ready to be used. All we need to do to use it is create a new instance of the DecimalNumberValidator class and start it running (remembering to provide it with a string to test) - like so:
DecimalNumberValidator testNet = new DecimalNumberValidator();
testNet.execute("1.234");
You can download the full source code for the DecimalNumberValidator and utility classes - online documentation for the utility classes is also available. The downloadable source code is more extensive than just that outlined here - but this discussion, the documentation and taking a look at the code for the DecimalNumberValidator class should be enough to prepare you for building your own Finite State Machines.