Visual Basic —

The Art of the State

An FSM is a virtual machine characterized by a set of internal states, a set of external events, and a set of transitions between the states. You might also hear FSMs referred to by the name finite state automata, deterministic finite automata, or simply state machines. FSMs can be used to model an entire application, a small part of it, or both, and they are extremely common in the design of real-time systems, compilers, and communications protocols. FSMs are ideal tools for representing event-driven programs such as GUIs.

States are labels assigned to particular sets of circumstances within the application. Although FSMs are often used to model the GUI part of applications, states are not forms, and events are not necessarily Visual Basic events. You generate a set of predefined events from real-world stimuli and apply them as inputs to the FSM to drive it through transitions into different states. Transitions can have arbitrary lists of actions associated with them, and these actions are executed as you drive the FSM from state to state by repeatedly applying events. An FSM is deterministic because each combination of state and event unambiguously defines the next state to move into.

An FSM can be represented as a state transition diagram or as a pair of tables, one table defining the next state to move into when a particular state/event combination is detected and the other table defining a list of actions to be performed along the way.

Figure 13-4 shows an FSM for a program to strip C comments out of a text stream. (Comments in C are delimited by /* and */.)

Figure 13-4 Comment stripper FSM

The bubbles in Figure 13-4 represent states, and the arrows represent transitions between states. Each transition is labeled with the event that stimulates it and the list of associated actions. One state is designated the start state, which is the initial state when the FSM starts to operate. Here is the FSM in tabular form:

State Table

State
Event Outside Starting Inside Ending
/ Starting Starting Inside Outside
* Outside Inside Ending Ending
Any other Char Outside Outside Inside Inside

Action Table

State
Event Outside Starting Inside Ending
/ N/A Print "/ " N/A N/A
* Print char N/A N/A N/A
Any other char Print char Print "/ "
Print char N/A N/A

These tables provide the basis for implementing an FSM as a program. An FSM program has the following elements:

  • A static variable to track the current state and a set of constants to represent all available states
  • A table or equivalent program network to look up a state/event pair and decide which state to move into
  • A set of constants to represent FSM events
  • A driver loop that captures real-world events and decodes the state/event pair