Overview

Code

Specifications

Time Chart

Overview

The model used for a state machine parallels the graph data structure: individual states are nodes in the graph, while transitions correspond to directed edges between nodes.  The user defines nodes with a node name, unique within the state machine.  Transitions are defined in terms of the source node name, destination node name, and a letter identifying each transition uniquely within the context of a given source node.  Transitions from a node to itself are allowed, as are multiple transitions between the same two nodes (triggered by different events).  A transition will occur when a particular event is fed into the machine.  Each event is associated with a
specific letter, which will trigger a given transition if it matches the letter identifying that transition.

This package effectively implements a deterministic finite state machine.  The user first builds the machine, then makes it operational and feeds it events.   The simulation must be stopped to change the properties (add/remove states and transitions).  It can either resume where it left off, or be reset to the original initial state.

A driver has been provided to allow automated testing of the library internals, specifically to support maintenance of this package.  This code should be run after any changes have been made to the library.  It has been designed to test a number of likely failure points and produces easily readable output, making it more user-friendly.

Code

Here is a list of the files:

State.java Specifications Here is a list of problems that we encountered and the solutions we chose:

• States that are never reached; states that are never left; states with no transitions. For problems like this, we assumed that the user is aware of the structure of the machine.  The machine will run if there is a state with no transitions pointing to it.  The machine will also run if a state only has transitions that return to itself.  States can be created without transitions leaving it.  These issues do not oppose the definition of our machine.
• Alphabet can be expanded and shrunk.  We did not require the user to define all events initially.  Events (letters) can be added and removed at any time (except while the simulation is running).
• Transition added to non-existant state; Initial state set to nonexistant state.  To keep the machine uniform, the only way to add a state is by using the addState method.  If other methods try to run using a state that does not exist, StateDoesNotExistException will be thrown.
• Events given during simulation when there is not a defined transition from the current state using that letter.  An exception will be thrown if the user enters a letter that does not have a transition defined for the current state.
• Remove state when transitions point to it.  An exception will be thrown.  This is how we dealt with the problem of removing a state and having transition(s) that points to null.  Another option would be removing all transitions that point to that state when it is removed.  We decided that valuable transitions could be lost, and we left it up to the user to remove transitions first.  (Note:  This has the problem of limiting the user in the order in which she builds the machine. Invalid states, even if only temporary, cannot exist.  In the end, this constant error checking allows the user to be sure that the machine is always valid.  It also prevents complicated error checks when startSimulation is called.)
• Add/remove states and transitions during simulation.  The user can only add and remove states and transitions when the simulation is not running.  Of course, you can stop the simulation, make the changes, and then restart where you left off.  (You can print the characteristics of the state while the simulation is running.  This is useful for error checking.)
• Initial state must exist.  The only check made before the simulation runs is that an initial state has been defined.  All other checking is done within the other methods.  This prevents an extremely complex checking when startSimulation is called.  Again, we have trusted the user to set up the machine as she wishes.
• User enters only string labels for states and letters.  To keep things simple for the user, the user only passes strings to the machine.  All objects are created within the FiniteStateMachine and State classes.
• Transitions do not use "println" but the sendEvent method returns type String.  We chose to implement a FiniteStateMachine class which did not output anything but silently maintained a finite state machine, and a separate MealyMachine class which inherits from FiniteStateMachine and prints its results to stdout.  This way a potential user of our code would have the option of either, and someone who wished to implement a graphical applet using a finite state machine would not be stuck with a class that only outputs things to the console.
• Transition already exists; State already exists.  We did not allow identical transitions or states to exist.  If a user tries to add a transition which uses the same starting state and the same letter as an existing transition, an exception is thrown.  The same is true for states with the same name.  On the other hand, transitions with the same starting and ending states triggered by different letters can exist.

Time Chart

---