Awesome
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:
- regular languages can be described with basic FSMs. Cf. regexp simulator
- morphological analysis can be performed by state transducers
- CFSMs can be used to model some classes of distributed systems
- extended hierarchical finite state transducers, or their statecharts extension, can be used to model user interface behaviour, or game agent behaviour
Reading
-
General
-
User interface modeling
- Horrocks, Ian. Constructing the User Interface with Statecharts. Boston, MA: Addison-Wesley, 1999
- User Interfaces You Can Trust with State Machines
- State Machines in React
- State Machines: Our First XState Machine
-
Model-based testing
-
Gaming
-
Distributed systems
Projects
-
JavaScript
-
Python
-
Erlang/Elixir
-
Other
- [Boost].SML
- Pretty sure there's a finite state machine implementation in every known programming language...