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 few special states at any time. The FSM can change from one state to another when it gets certain inputs. This change is called a transition. An FSM is made up of a list of its states, its starting state, and the inputs that cause each transition.

The behavior of state machines can be seen in many everyday devices that do a set sequence of actions based on events. Simple examples are vending machines, which give out products when the right coins are put in; elevators, which stop at floors people request; traffic lights, which change when cars are waiting; and combination locks, which need the right numbers in the right order.

The finite-state machine has less power to compute than other models like the Turing machine. This is because an FSM's memory is limited by how many states it has. FSMs are studied in the field of automata theory.

Example: coin-operated turnstile

A turnstile is a gate used to control entry to places like subways and amusement park rides. It has three arms that block 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. This table 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. 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 useful in many areas, like 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 show how programs and systems behave, design digital hardware, and create rules for networks.

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 mix ideas like hierarchical state machines, flow graphs, and truth tables into one system. These methods work like Harel’s original state machines. They let states be nested inside each other, have separate regions that can happen at the same time, and actions that happen when states change.

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 making it simpler by using fewer states while still keeping it working the same way. One of the quickest ways to do this is with the Hopcroft minimization algorithm. Other ways include using an implication table or the Moore reduction procedure. For some types of machines without cycles, this can be done fast using linear time.

Implementation

Finite-state machines can be used in both hardware and software. In hardware, they are made with parts like logic gates and flip-flops to store and change states. In software, they help make programs by breaking tasks into steps and responses to events. They are also used in compilers. Compilers are tools that change 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