Finite-state machine

Lore & Background

A finite-state machine is defined by a list of its states, its initial state, and the inputs that trigger each transition. There are two types: deterministic finite-state machines and non-deterministic finite-state machines, and for any non-deterministic one an equivalent deterministic one can be constructed. The turnstile is a classic example: it has two states (Locked and Unlocked) and two inputs (coin and push), with transitions that model the locking and unlocking mechanism. FSMs have less computational power than Turing machines because their memory is limited by the number of states. They have the same power as a Turing machine restricted to read-only operations moving left to right. FSMs are studied in automata theory and are significant in electrical engineering, linguistics, computer science, philosophy, biology, mathematics, video game programming, and logic. Physical realizations of FSMs often produce outputs used as control signals. Their behavior is observed in many devices that perform predetermined sequences of actions based on events, such as vending machines, elevators, traffic lights, and combination locks. UML state machines and SDL state machines are among the representations that extend traditional FSM concepts.

Reader's Guide

Finite-state machines are a foundational concept in automata theory and the theory of computation. They provide a simple yet powerful framework for modeling systems that exist in a finite number of states and respond to inputs with state transitions. Their significance lies in their wide applicability: from hardware design and software engineering to compilers, network protocols, and computational linguistics. FSMs are classified into acceptors, classifiers, transducers, and sequencers. Acceptors, for instance, define regular languages by accepting or rejecting input strings based on whether the final state is an accepting state. The ability to convert any non-deterministic FSM into a deterministic one is a key theoretical result. While limited in computational power compared to Turing machines, FSMs are essential for understanding more complex models and for practical implementation in control systems and digital logic. Their legacy endures in both theoretical computer science education and real-world device design.

Did You Know?

• A finite-state machine can be in exactly one of a finite number of states at any given time.
• For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.
• A finite-state machine has the same computational power as a Turing machine restricted to read-only operations moving left to right.
• The turnstile state machine has two states (Locked and Unlocked) and two inputs (coin and push).