State machine
Overview
A state machine, also known as a finite state machine (FSM), 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 external 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 conditions for each transition.
Types of State Machines
State machines can be divided into two types: deterministic (DFSM) and non-deterministic (NDFSM).
Deterministic Finite State Machine
A DFSM is a state machine where for each pair of state and input symbol there is one and only one transition to a next state. DFSMs are easier to analyze than their non-deterministic counterparts, as the state of the machine can be determined by its current state and sequence of inputs.
Non-deterministic Finite State Machine
A NDFSM is a state machine where for each pair of state and input symbol, there could be several possible next states. This type of FSM does not determine its transitions on just the current state and the current input symbol. Instead, it depends on an additional setting.
State Machine Diagrams
State machine diagrams, also known as state diagrams, are used to illustrate the states an object or interaction may be in, as well as the transitions between those states in the context of system behavior.
Applications of State Machines
State machines have vast applications in various fields of computer science and engineering. Some of the most common applications include:
Computer Science
In computer science, state machines are used in computing algorithms, logic circuits, computer software engineering and in virtually all sequential logic.
Telecommunications
In telecommunications, state machines are used to describe signal protocols.
Linguistics
In linguistics, state machines are used in natural language processing.