Skip to content

Latest commit

 

History

History
101 lines (78 loc) · 8.02 KB

README.md

File metadata and controls

101 lines (78 loc) · 8.02 KB
Raw

State Machines

What is it?

There are many variants in definitions of finite state machines, depending on whether one views them as language acceptors/generators (automata), or machines that react with their environment and produce output (eg. Mealy and Moore machines, I/O automata), or logical models (Kripke structures) etc. [...] In practice, several extensions are useful to enhance the expressive power and to describe more complex systems more efficiently

Source: Hierarchical State Machines, Mihalis Yannakakis, Bell Laboratories, 2000

A basic finite state machine features states, transitions and accept external inputs. Basic FSMs can be extended by adding outputs, memory, hierarchy, concurrency and communication. A machine with outputs will produce an output for each external input it receives. A machine with memory will hold track of a set of internal variables, which it can update on receiving external inputs. A machine with hierarchy contains sub-machines and can delegate the processing of external inputs to those sub-machines. A machine featuring concurrency and communication may contain a set of machines, which concurrently process external inputs and communicate together. Extensions add expressivity to the machine at the cost of higher complexity.

According to the extensions added to the basic state machine formalism, the following terminology is commonly used:

Extension Terminology Features
- basic finite state machine (FSM) states, transitions
output basic finite state transducer (FST) states, transitions, output functions
output depending only on state Moore machine states, transitions, output functions
output depending on state and input Mealy machine states, transitions, output functions
memory extended finite state machine (EFSM) states, transitions, set of variables, guards, memory update functions
memory + output extended finite state transducer (EFST) states, transitions, set of variables, guards, memory update functions, output functions
hierarchy hierarchical finite state machine (HFSM or HSM) tree of states, transitions
hierarchy + memory extended hierarchical finite state machine (EHFSM or EHSM) tree of states, transitions, set of variables, guards, memory update functions
hierarchy + memory + outputs extended hierarchical finite state transducer (EHFST or EHST) tree of states, transitions, set of variables, guards, memory update functions, output functions
concurrency communicating finite state machines (CFSM) set of state machines, communication protocol, concurrency semantics
concurrency (broadcast communication) + hierarchy statecharts set of hierarchical state machines, history pseudo states, broadcast communication protocol, concurrency semantics tightly integrated to the FSM semantics
concurrency + hierarchy communicating hierarchical finite state machines (CHFSM or HCFSM) set of hierarchical state machines, communication protocol, concurrency semantics

What is it used for?

Finite state machines constitute one of the most fundamental modeling mechanisms in Computer Science. They have been widely used to model systems in a wide variety of areas, including sequential circuits, event-driven software, communication protocols and many others.

Source: Hierarchical State Machines, Mihalis Yannakakis, Bell Laboratories, 2000

Extensions to the basic state machine formalism can be chosen based on the characteristics and complexity of the system or computation to model:

Reading

Projects

Examples