Finite-State Machines FSM: A Short Note with Core Theory and Examples | AI Research

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

Verified Sources

Sep 12, 2026

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).

Pro Tip

When writing a short note, define the 5-tuple first (states, alphabet, transition, start, accepting) and then briefly explain how processing and acceptance work.

How an FSM runs on an input

Start

Initialize

Place the machine in start state $q_0$ before reading input."

Transition step

Read symbols

For each input symbol, update the state using $\u03b4$ ."

Accept/Reject

Finish

After the last symbol, accept iff the current state is in $F$ ."

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.

Construct (and describe) an FSM for a simple language property

1
Step 1
Example: recognize strings over {0,1} that contain an even number of 0s.
2
Step 2
Use two states representing parity: $q_e$ (even # of 0s so far) and $q_o$ (odd # of 0s so far).
3
Step 3
Start in $q_e$ because before reading input, the count of 0s is even.
4
Step 4
On input 0: toggle parity ( $q_e \u2192 q_o$ , $q_o \u2192 q_e$ ). On input 1: parity unchanged.
5
Step 5
Accept in $q_e$ and reject in $q_o$ after the entire input is consumed.

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.

FSM variants: what they base output/next-state on

Conceptual comparison (not a performance benchmark)

Common clarifications (for a “short note” answer)

Knowledge Check

Question 1 of 4

Q1Single choice

In the standard DFA definition $M=(Q,\Sigma,\delta,q_0,F)$ , what does $\delta$ represent?

The set of accepting states

The transition function mapping (state, input) to next state

The input alphabet

The start state

Explore Related Topics

Write Short Notes on UML Diagrams

Closure Properties of Context-Free Languages (CFLs)

Understanding Digital Counters: Principles, Types, and Applications

Digital counters are sequential circuits built from cascaded flip‑flops that count input events, with a maximum modulus of 2ᴺ for N stages, and are classified as asynchronous (ripple) or synchronous based on clock distribution.

Asynchronous counters cascade flip‑flop clocks, causing cumulative propagation delay and limiting maximum frequency.
Synchronous counters receive the clock simultaneously, using combinational logic to eliminate ripple delay and support higher speeds.
Designing a synchronous Mod‑6 counter involves defining the state sequence, creating excitation tables, simplifying with Karnaugh maps, and wiring JK flip‑flops with derived logic.
Ring counters yield N states; Johnson counters double this to 2N states.
Prevent glitches and lock‑out by using Gray‑code sequencing, output strobes, and ensuring unused states redirect to the main count sequence.

Browse all research articles