Finite State Machine (FSM)

The finite-state machine (FSM) simulator is radically different from the other VisualSim simulators. The entities in this simulator represent not block/actor but rather state and the connections represent transitions between states. Execution is a strictly ordered sequence of state transitions. The FSM simulator leverages the built-in Expression Language in VisualSim to evaluate guards, which determine when state transitions can be taken. FSM models are excellent for control logic in embedded systems, particularly safety-critical systems. FSM models are amenable to in-depth formal analysis, and thus can be used to avoid surprising behavior.

FSM models have a number of key weaknesses. First, at a very fundamental level, they are not as expressive as the other models of computation described here. They are not sufficiently rich to describe all partial recursive functions. However, this weakness is acceptable in light of the formal analysis that becomes possible. Many questions about designs are decidable for FSMs and undecidable for other models of computation. A second key weakness is that the number of states can get very large even in the face of only modest complexity. This makes the models unwieldy.

Both problems can often be solved by using FSMs in combination with concurrent models of computation. This was first noted by David Harel, who introduced Statechart formalism. Statecharts combine a loose version of synchronous-reactive modeling (described below) with FSM. FSMs have also been combined with differential equations, yielding the so-called hybrid systems model of computation.

The FSM simulator in VisualSim can be hierarchically combined with other simulators. We call the resulting formalism “*charts” (pronounced “starcharts”) where the star represents a wildcard. As most other simulators represent concurrent computations, *charts model concurrent finite state machines with a variety of concurrency semantics. When combined with CT, they yield hybrid systems and modal models. When combined with SDF (described below), they yield something close to Statecharts.