The FSM Package

User Documentation

Author: Jon Parise
Date: 2004-01-30
Revision: 1.1


1   About the FSM Package

The FSM Package implements a Finite State Machine. In addition to maintaining state, this FSM also maintains a user-defined payload. therefore effectively making the machine a Push-Down Automata (a finite state machine with memory).

This code is based largely on Noah Spurrier's excellent FSM Python class.

2   Building a Finite State Machine

The first step in building a Finite State Machine involves listing the finite set of states. Then, all of the permissible transitions between these states must be defined. A symbol and an optional callback function are associated with each transition. The input processing routine will attempt to match its current symbol against the list of registered transitions. If it a transition from the current state using that symbol is found, the current state will be updated to the new state specified by the transition and, if one has been specified, the associated callback function will be invoked.

2.1   Creating A New FSM Object

Start by including the FSM package in your script:

require 'FSM.php';

When constructing a new FSM object, you must specify the machine's initial state and provide a payload container. The payload will be passed to all of the callback functions, allowing you to provide them with state information without (ab)using global variables.

In this example, we pass an array representing a stack as the payload. The machine's initial state is set to START:

$stack = array();
$fsm = new FSM('START', $stack);

2.2   Defining Transitions

We'll need to define some transitions in order to make our machine useful. Let's assume our machine has two additional states: MIDDLE and END. Here's how we would define transitions to move us from START to MIDDLE to END:

function FirstCallback($symbol, $payload)
    echo "First Transition\n";

function SecondCallback($symbol, $payload)
    echo "Second Transition\n";

$fsm->addTransition('FIRST', 'START', 'MIDDLE', 'FirstCallback');
$fsm->addTransition('SECOND', 'MIDDLE', 'END', 'SecondCallback');

Our machine is now aware of three states (START, MIDDLE, END) and two symbols (FIRST, SECOND). Two transitions (START to MIDDLE, and MIDDLE to END) have been defined and associated with callbacks. The following code will process the symbols FIRST and SECOND and move us from our initial state (START) through the MIDDLE state to the END state:


The processing routine will invoke our two callbacks along the way, as well, resulting in the following being printed:

First Transition
Second Transition

2.3   Setting Default Transitions

Now we'll set up a default transition. This transition will be used whenever the processing routine cannot find a better match for the current state and symbol. For our example, we'll consider this an error and print a warning for the user:

function ErrorCallback($symbol, $payload)
    echo "This symbol does not compute: $symbol\n";

$fsm->setDefaultTransition('START', 'ErrorCallback');

Now let's process our symbols in an unexcepted order:


Because the SECOND transition doesn't specify START as its initial state, the default transition will be used and the error callback will be invoked. The FIRST transition will work as expected, however, because the machine will remain in the START state.