Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA) is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.

The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines, which dispense products when the proper combination of coins is deposited; elevators, whose sequence of stops is determined by the floors requested by riders; traffic lights, which change sequence when cars are waiting; and combination locks, which require the input of a sequence of numbers in the proper order.

The finite-state machine has less computational power than some other models of computation such as the Turing machine. This is because an FSM's memory is limited by the number of states it has. FSMs are studied in the more general field of automata theory.

Example: coin-operated turnstile

A turnstile is a gate used to control access to places like subways and amusement park rides. It has three rotating arms that block the entry until someone pays. When you put a coin or token into the slot, the arms unlock, and one person can pass through. After they pass, the arms lock again.

We can think of the turnstile as a state machine with two states: Locked and Unlocked. If it is locked, pushing the arms does nothing. But putting in a coin changes the state to unlocked. In the unlocked state, putting in more coins does not change anything, but when someone pushes through, the state goes back to locked. This can be shown in a table or a diagram called a state diagram, where circles represent states and arrows show how the machine changes from one state to another.

Main article: State diagram

Concepts and terminology

A state describes how a system is set up before it does something. A transition is what the system does when certain conditions are met or when it receives a specific signal. For example, think of using an audio system. If you're listening to the radio (the system is in the "radio" state) and press a button to go to the next station, that's a transition. But if you're playing a CD (the system is in the "CD" state) and press the same button, it will skip to the next track instead. The same button does different things based on what the system is currently doing.

Sometimes, special actions can also be linked to states. An entry action happens when the system starts a new state, and an exit action happens when the system leaves a state.

Representations

For an introduction, see State diagram.

Several state-transition table types are used. The most common way to show how a finite-state machine works is by using a table that lists the current state and input, and shows the next state it will move to.

The Unified Modeling Language has a special way to describe state machines called UML state machines. These help fix some problems of regular finite-state machines while keeping their good points. UML state machines add ideas like hierarchically nested states and orthogonal regions. They mix features from both Mealy machines and Moore machines.

Usage

Finite-state machines are important in many areas, such as electrical engineering, computer science, and video game programming. They help us understand how things change and react to different inputs. In computer science, they are used to model how programs and systems behave, design digital hardware, and create network protocols.

Classification

Finite-state machines can be divided into different types based on what they do. Acceptors, also called detectors or recognizers, decide if a string of symbols is accepted or not. They have special states called accepting states. If the machine ends in an accepting state after reading all the symbols, the string is accepted.

Transducers produce output based on input and/or current state, useful for control tasks and language processing. Two common types are Moore machines, where output depends only on the state, and Mealy machines, where output depends on both input and state.

Alternative semantics

There are different ways to describe state machines. Some tools combine ideas like hierarchical state machines, flow graphs, and truth tables into one system. These methods, similar to Harel’s original state machines, allow for nested states, separate regions that can happen at the same time, and actions that occur during state changes.

Mathematical model

A finite-state machine is like a simple computer that can only be in one state at a time. It changes from one state to another based on inputs it receives. These machines help us understand how computers and other systems can process information step by step.

This model shows how such machines work using sets of symbols, states, and rules for moving between states. They are useful in many areas, from designing computers to understanding how languages work.

Optimization

Main article: DFA minimization

Optimizing a finite-state machine means finding a simpler version with fewer states that still works the same way. One of the fastest ways to do this is called the Hopcroft minimization algorithm. Other methods include using an implication table or the Moore reduction procedure. For certain types of machines without cycles, this can even be done quickly in linear time.

Implementation

Finite-state machines can be used in both hardware and software. In hardware, they are built using parts like logic gates and flip-flops to store and change states. In software, they help create programs by breaking tasks into steps and responses to events. They are also used in compilers, which are tools that turn code written by people into a form that computers can understand. These machines help read and organize the code into meaningful pieces.

Main articles: Automata-based programming, Event-driven finite-state machine, Virtual finite-state machine, State design pattern