Finite State Machine
- Model of computation built from a finite set of states and transitions.
- The machine occupies exactly one state at a time and changes state only when specific inputs occur.
- Commonly used to design algorithms and digital logic, and to control systems with discrete modes.
Definition
Section titled “Definition”A finite state machine (FSM) is a mathematical model of computation used to design algorithms and digital logic. It consists of a finite number of states, which are represented by circles in a state diagram, and a set of transitions between those states, which are represented by arrows. A finite state machine can be in only one state at a time, and it can transition from one state to another only in response to a specific input.
Explanation
Section titled “Explanation”An FSM describes behavior as a collection of discrete states and the allowed transitions between them. States are typically shown as circles in a state diagram and transitions as arrows labeled by the triggering inputs. At any moment the machine is in a single state; when an input matching a transition occurs, the machine moves along that transition to the next state. This structure makes the machine’s response to inputs predictable and well defined.
Examples
Section titled “Examples”Vending machine
Section titled “Vending machine”The vending machine has a finite number of states, such as “idle,” “accepting payment,” and “dispensing product.” It also has a set of transitions between those states, such as “insert coin” or “select product.” When the vending machine is in the “idle” state and a user inserts a coin, the machine transitions to the “accepting payment” state. When the user then selects a product, the machine transitions to the “dispensing product” state, and so on.
Traffic light
Section titled “Traffic light”The traffic light has a finite number of states, such as “red,” “yellow,” and “green.” It also has a set of transitions between those states, such as “time expired” or “emergency vehicle detected.” When the traffic light is in the “red” state and the time for that state expires, the light transitions to the “green” state. If an emergency vehicle is detected, the light may transition to the “yellow” state and then to the “red” state to allow the emergency vehicle to pass.
Use cases
Section titled “Use cases”- Performing specific tasks such as dispensing a product or controlling traffic in a predictable, reliable, and efficient way.
Related terms
Section titled “Related terms”- State diagram
- Transitions
- Algorithms
- Digital logic