Tutorial - General History and Definition of Finite State Machines

HOME

TUTORIALS

tutorials

Staccato™ provides continuous and direct execution of both Mealy and Moore Finite State Machines. This gives you complete flexibility during the design of an embedded software system.

To learn how to use these concepts in your embedded software system AND earn IEEE Continuing Education Units (CEUs)

Click here...

Tutorial 4: A General History and Definition of Finite State Machines

For a formal definition of Finite State Machines, see

National Institute of Science and Technology (NIST)

or Wikipedia

Mealy Machine Moore Machine

Finite State Machines, or automata, originated in computational theory and mathematical models in support of various fields of bioscience. However, their popularity today in the computer science and engineering fields can be attributed to the pioneering efforts of George H. Mealy and Edward F. Moore performed at Bell Labs and IBM (circa 1960s). Mealy and Moore's Finite State Machine concepts proved valuable in two important engineering disciplines: language parsing (compilers) and sequential circuit design. Gradually, the software engineering community partially adopted FSM concepts as more structured analysis and design methods were needed to validate this originally arcane endeavor.

Finite State Machine logic was used successfully in various aspects of computer programming and in 1987, David Harel published Statecharts: A Visual Formalism for Complex Systems. Harel embellished the Mealy and Moore paradigm with the concept of hierarchical finite state machines and concurrency/orthogonality. Although Harel did not specify Statechart implementation, many vendors used his work as the basis for products offering visual design of FSMs with auto-code generation for (embedded) software systems. Statecharts eventually became part of the Unified Modeling Language (UML 2.0), a step forward in the recognition of the usefulness of Finite State Machines in general-use software applications. However, most of these Statechart-based tools presume the FSMs of the resulting application are to be run within the framework of an enterprise or real-time operating system (OS/RTOS).

Definition and Operation...

It is common to distinguish Finite State Machines as either a Mealy or Moore machine. The difference between the two machines, as we shall explore later, are noteworthy, but not necessarily paramount to successful Finite State Machine design for software application architecture, but likely important in sequential circuit design.

Finite State Machines (Mealy and Moore) are defined as sharing the following characteristics:

a finite set of defined states, one of which being defined as the initial state of the machine
a set of defined inputs
a set of defined outputs
a set of transitions between selected states, and
the machine is said to be in a single state at any instant of time

The basic operation of a Finite State Machine system is this: as the system is in one of the defined states at any instant of time, it will react to specified (external) inputs or (internal) conditions with specified actions, and transition to another defined state, or remain in its current state, depending on the design. For a Mealy machine, the transition will be associated with an output. For a Moore machine, the output occurs within the next state. For this reason, Finite State Machines are often called 'reactive' systems. Inputs are also called events. Typical events may be: a message received from another state machine, a simple event flag set by another state machine, or the expiration of a time interval. Likewise, outputs may be: sending a message to another state machine, setting an event flag for another state machine to respond to, or starting a timed interval. Also, multiple unique transitions are allowed from one state to other defined states. For software FSMs, each state will have its unique source code logic to process events, perform actions and output, and to effect state transitions. A complete system may be comprised of one or more Finite State Machines, as determined by the partitioning process performed during the initial design or analysis.

Finite State Machines are generally depicted as a State Diagram, represented graphically with two symbols: the state bubble and the transition arrow. States are labeled or numbered and both inputs and outputs are described textually. At any instant of time, a state machine is in its current state. Depending on the specified input events and conditions, a transition to the next state will occur. Finite State Machines are considered deterministic if all transitions to next states are unique to a given state and its inputs. Most useful FSMs are fully deterministic, making them ideal for embedded systems software and the process of validation and verification.

A Mealy State Machine...A Mealy Machine allows for output actions to accompany each state transition as shown in the diagram. When the current state is 'A', and if the 'Input' event occurs, the 'Output' action is performed and a transition to state B (the next state) occurs. In this example, state 'A' is also the initial state for this machine. Note that if additional events were significant to state 'A', additional outputs would be specified and transitions to state 'B' or any other additional states would be specified.

Basic Mealy Finite State Machine State Diagram example

Basic Moore Finite State Machine State Diagram Example

A Moore State Machine...

A Moore Machine is similar to the Mealy Machine, however the Output is moved forward to the next state, and occurs within state 'B' as shown in the diagram.

Although the Mealy Machine model may be more flexible than the Moore Machine, it is the needs of the system being analyzed or designed that determines which of the two is most suitable. Note that a given state machine may be comprised of both Mealy and Moore models, if such a design meets the functional requirements of the system. Also, be aware that both Mealy and Moore Machines can be logically converted to the other. The point here is that the correct state logic required for efficient operation is what's important; the resulting machine archetype (Mealy or Moore) should be only a secondary observation.

See a Staccato™ Basic Task State Diagram here...

Staccato™ provides continuous and direct execution of both Mealy and Moore Finite State Machines. This gives the designer complete flexibility during the design of an embedded software system.

With an understanding of this informal historical perspective of Finite State Machines, click here for the Current State of Finite State Machine usage in Software...