Finite State Machine

Overview

A Finite State Machine (FSM), also known as a finite state automaton, 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 inputs that trigger each transition.

Definition

A deterministic finite automaton (DFA) is formally defined as a 5-tuple, (Q, Σ, δ, q₀, F), where:

Q is a finite set of states.
Σ is a finite set of input symbols called the alphabet.
δ is a transition function (δ: Q × Σ → Q).
q₀ is an initial (or start) state, where q₀ ∈ Q.
F is a set of accept states (or final states), where F ⊆ Q.

Key Concepts

Deterministic vs. Non-deterministic: In a Deterministic Finite Automaton (DFA), for each state and input symbol, there is exactly one transition to a next state. In a Non-deterministic Finite Automaton (NFA), there can be multiple (or no) transitions for a given state and input symbol, including transitions without reading any input symbol (ε-transitions). Every NFA can be converted to an equivalent DFA.
Acceptance: An FSM accepts a string of symbols if, after processing all symbols in the string sequentially, the machine ends up in an accept state. The set of all strings accepted by an FSM is called the language recognized by the machine.
Regular Languages: The class of languages that can be recognized by Finite State Machines are exactly the Regular Languages. These are the same languages that can be described by Regular Expressions.

Historical Context

The concepts underlying finite state machines were developed by several researchers in the mid-20th century. Warren McCulloch and Walter Pitts introduced a model of neural networks in 1943 that laid the groundwork for finite automata theory. Later, in 1956, Edward F. Moore and George H. Mealy independently developed formal models of state machines (now known as Moore machines and Mealy machines, respectively) that produce outputs. These early models became fundamental in theoretical computer science, compiler design, and hardware engineering.

Applications

Lexical Analysis: Compilers use FSMs to break source code into meaningful tokens (like keywords, identifiers, and operators).
Regular Expressions: Regex engines often compile patterns into NFAs or DFAs to efficiently match strings against the pattern.
Hardware Design: Sequential logic circuits and digital systems are designed using FSMs to control state transitions based on clock cycles and inputs.
Game Development: AI character behaviors (e.g., patrolling, chasing, attacking) are frequently implemented using FSMs.
Protocol Parsing: Network protocols use state machines to manage connection states (like TCP's SYN-SENT, ESTABLISHED, FIN-WAIT).

Related Concepts

Regular Expressions — an algebraic notation for describing the same languages recognized by FSMs.
Turing Machines — a more powerful model of computation that can write to memory, unlike FSMs.
Pushdown Automata — FSMs augmented with a stack, capable of recognizing context-free languages.

Finite State Machine