Finite-state machine

A finite-state machine (FSM) is a mathematical model of computation. It is an abstract machine that exists in exactly one of a finite number of states at any given time. These states represent the current status of a system while it waits for an event. When the machine receives a specific input, it can undergo a transition. A transition is the process of changing from one state to another.

This model is fundamental to automata theory, which is the study of machines and their computational abilities. FSMs are essential for designing systems that must follow a predetermined sequence of actions based on external events.

To understand the mechanism, consider the inputs and transitions that define an FSM. An FSM is formally defined by a list of its states, its initial state, and the inputs that trigger each transition. For example, a turnstile can be modeled as a state machine with two states: Locked and Unlocked.

In the Locked state, the input of a coin triggers a transition to the Unlocked state. However, the input of a "push" while in the Locked state results in no change. Once the machine is Unlocked, a "push" input triggers a transition back to the Locked state.

This behavior can be mapped using a state-transition table or a state diagram. In a state diagram, nodes represent states and directed edges, or arrows, represent the transitions triggered by inputs.

There are two primary types of finite-state machines: deterministic and non-deterministic. In a deterministic finite-state machine (DFSM), each input leads to exactly one specific next state. This makes the behavior predictable and certain. In a non-deterministic finite-state machine (NFSM), an input might allow for multiple possible next states. Despite this difference, any non-deterministic machine can be converted into an equivalent deterministic one. This mathematical equivalence allows engineers to use non-deterministic models to simplify complex designs before implementing them as deterministic systems.

FSMs are categorized by their specific functions into four groups: acceptors, classifiers, transducers, and sequencers. Acceptors, also known as recognizers, produce a binary output to indicate if an input sequence is accepted or rejected.

An acceptor determines if a sequence of symbols belongs to a formal language, known as a regular language. For instance, a machine can be designed to accept only binary strings that contain an even number of zeros.

Classifiers are a more complex version of acceptors that produce n-ary output, where n is greater than two. Sequencers are a specific subclass that use a single-letter input alphabet to generate sequences.

Transducers are machines that produce outputs based on inputs and current states. They are used heavily in control applications and computational linguistics. There are two major models of transducers: Moore machines and Mealy machines. In a Moore machine, the output depends solely on the current state.

This is useful for simplifying behavior, such as an elevator door that signals "open" or "closed" based on its state. In a Mealy machine, the output depends on both the current state and the input received.

Mealy machines often require fewer states to perform the same task as a Moore machine.

Historically and theoretically, FSMs occupy a specific place in the hierarchy of computational power. An FSM has less computational power than a Turing machine. This limitation exists because an FSM's memory is strictly limited by its finite number of states. A Turing machine can perform tasks that an FSM cannot because it has much more flexible memory. However, an FSM is equivalent in power to a Turing machine that is restricted to only "read" operations and can only move its head in one direction, from left to right.

Today, the applications of finite-state machines are vast and diverse. They are used in electrical engineering to design digital hardware and in computer science for software engineering and network protocols. In linguistics, they help model how languages function.

You can see FSM logic in everyday devices like vending machines, elevators, and traffic lights. Even a combination lock is a physical manifestation of a state machine, as it requires a specific sequence of inputs to reach the final state. From video game programming to biology, these mathematical models help us organize and understand complex, reactive systems.