Finite-State Machines (FSM): A Short Note with Core Theory and Examples

A finite-state machine (FSM) is a mathematical model of computation used to describe systems with a limited number of modes (states). At each step, the machine reads an input symbol and updates its current state according to a transition rule. FSMs are especially important because they precisely capture the class of regular languages and appear in many practical designs like lexical analyzers, protocol logic, and digital circuits.

The formal structure is often given as a 5-tuple. A deterministic finite automaton (DFA) is commonly defined by: $M=(Q,\Sigma,\delta,q_0,F)$ where $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\delta$ is the transition function, $q_0$ is the start state, and $F$ is the set of accepting (final) states.

A DFA processes an input string by starting in $q_0$ and repeatedly applying $\delta$ to determine the next state; acceptance occurs if the final state after consuming the entire string lies in $F$.

Key terms to remember

• state: one of the machine’s finite configurations
• alphabet
• transition function
• start state
• accepting state

Note: Many textbooks also describe nondeterminism (NFA) and show that NFAs and DFAs recognize the same class of languages (regular languages).

DFA vs NFA vs “output” FSMs (Mealy/Moore)

FSMs appear in multiple variants depending on determinism and whether outputs are produced during operation.

DFA vs NFA (nondeterminism)

• In a nondeterministic finite automaton (NFA) the transition function allows multiple next states for the same input symbol.
• The usual definition of acceptance for an NFA is existential: the input is accepted if at least one computation path ends in an accepting state after consuming the entire string.

Mealy vs Moore machines (FSM with outputs)

When an FSM produces outputs, it can be modeled as:

• A [Mealy machine]{def="FSM where outputs are associated with transitions}”: output depends on the current state and input symbol (on edges).
• A [Moore machine]{def="FSM where outputs are associated with states}”: output depends only on the current state (in nodes).

Why this matters

• In protocol/control systems, Mealy machines can react immediately to inputs (output on transition).
• In hardware design and control, Moore machines are often preferred for stable outputs tied to states.

Example short note (pattern-recognition style)

Here is a compact “short note” you can adapt:

A finite-state machine (FSM) is a formal model for computing with a finite number of states. A DFA can be described as a 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$, where $Q$ is the set of states, $\Sigma$ the input alphabet, $\delta$ the transition function, $q_0$ the start state, and $F$ the set of accepting states. The machine processes an input string left-to-right by repeatedly updating its current state using $\delta$. The input is accepted if after the last symbol, the machine is in a state from $F$.

More general variants include NFAs (multiple possible transitions per symbol) and output machines such as Mealy and Moore machines, which are useful when outputs must be generated during processing.