Finite State Machines (FSM) – Miguel Armengol

Definition

A Finite State Machine is a formal model of computation defined by a finite set of states, a finite set of input events, a transition function, an initial state, and a set of terminal states.

FSM = (S, E, T, s0, F)

S — finite set of states
E — finite set of events
T — transition function
s0 — initial state
F — terminal states

At any moment, the system is in exactly one state. A transition fires when an event arrives and T(current_state, event) produces next_state.

This note covers the FSM as a behavior modeling formalism for agent decision-making, alongside the other topics in this submodule (Hierarchical State Machines, Behavior Trees, Goal-Oriented Planning, PDDL, HTN, Rule Engines, Constraint Solving).

It does not cover how an FSM is executed in production — durability, retries, idempotency, approval gates, tool authority. Those concerns are covered in 1.1.1 State machines in agentic systems.

Note	Lens	Question answered
1.1.1	Distributed systems thinking	How is a state machine run safely?
1.2.1	Planning + decision systems	What is the formal model? Why FSM vs others?

Core Properties

Finite state space

The set of legal states is fixed and explicitly enumerated.

ready
classifying
classified_simple
classified_complex
classified_unknown

The system cannot exist outside this set. Undefined states are invalid by construction.

Single active state

A classical FSM has exactly one active state at a time.

Concurrent or nested active states require Hierarchical State Machines or Statecharts (covered in the Hierarchical State Machines topic).

Explicit transition rules

Transitions are declared, not inferred.

classifying + SIMPLE   → classified_simple
classifying + COMPLEX  → classified_complex

If a transition is not defined, it does not exist.

Determinism

For a deterministic FSM:

T: S × E → S

(current_state, event) maps to exactly one next_state.

A non-deterministic FSM (NFA) maps to a set of possible next states:

T: S × E → P(S)

Agentic systems use deterministic FSMs by default. Non-determinism is introduced through guards (deterministic predicates over context) or through external decisions (an LLM choosing a transition from a finite allowed set).

Formal Vocabulary

State

A state is a named, discrete execution condition.

Naming convention: states are nouns describing what the system is (waiting, planning), not what it did (requested, processed).

Event

An event is an explicit named signal that may trigger a transition.

Naming convention: events are verbs or signals in upper case (USER_MESSAGE_RECEIVED, PLAN_READY, TIMEOUT).

Transition

A transition is a tuple (source_state, event, target_state) permitted by T.

Implicit transitions are forbidden. Every state change must correspond to a declared transition.

Guard

A guard is a deterministic boolean predicate over context that must be true for a transition to fire.

classifying + COMPLEX [ confidence > 0.8 ] → classified_complex

Guards are pure logic. They are not LLM judgment.

Context

Context is extended state stored outside the finite state.

State is the discrete control variable. Context holds operational data.

{
  "confidence": 0.82,
  "input_id": "abc-123"
}

Rule:

states describe behavior
context stores data

This separation is what keeps S finite while still allowing rich computation.

Terminal state

A terminal state is a state with no outgoing transitions.

classified_simple
classified_complex
classified_unknown

Every FSM model must declare its terminal states explicitly.

Worked Example: Triage Classifier

A small FSM that models a single decision step. The point is to show the model, not the runtime.

States:

ready
classifying
classified_simple
classified_complex
classified_unknown

Events:

INPUT_RECEIVED
SIMPLE
COMPLEX
UNKNOWN

Transitions:

ready + INPUT_RECEIVED → classifying

classifying + SIMPLE   → classified_simple
classifying + COMPLEX  → classified_complex
classifying + UNKNOWN  → classified_unknown

The FSM models what the agent decides. It says nothing about how the system runs the decision, persists results, or handles retries — those are orchestration concerns covered in 1.1.1.

The decision itself may be produced by an LLM, a classifier, or a rule. The FSM is independent of the producer.

Formal Properties

FSM models support:

enumerable trajectories — every legal sequence is a path through a known graph
reachability analysis — which states are reachable from a given initial state
equivalence checking — whether two FSMs accept the same set of trajectories
coverage testing — every transition is testable in isolation

These properties are the basis for testing, certification, and verification of agent behavior. Behaviors expressed as ad-hoc prompt loops do not have these properties.

FSM Among Behavior Formalisms

FSM is one of several formal models for agent decision-making. The 1.2 submodule compares them directly.

Formalism	Strength	Weakness	When to use
FSM	Simple, finite, auditable	State explosion with branching	Small, finite, well-understood behaviors
Hierarchical State Machine	Reuse, nesting, parent fallback	More complex tooling	Multi-mode systems with shared transitions
Behavior Tree	Modular, reactive, composable	Harder to express long-lived state	Game AI, robotics, reactive agents
Rule engine	Declarative, easy authoring	Conflict resolution complexity	Domain logic authored by non-engineers
Goal-oriented planning	Adaptive, novel sequences	Planning cost, partial observability	Open-world tasks, novel goal combinations
PDDL / HTN	Formal, expressive, decomposable	Heavy modeling effort, slow at scale	Robotics, logistics, formal task planning

Each row is a separate topic in this submodule.

FSM is the right default when:

the state space is small
the state space is finite
transitions are well understood
behavior must be auditable
behavior is authored by engineers

It is the wrong default when:

behaviors must compose at runtime
state explodes combinatorially
authoring is performed by non-engineers
the agent must plan novel sequences

When FSM Is Not Enough

State explosion is the classical failure mode. If a system has N independent boolean modes, a flat FSM requires 2^N states to represent every combination.

Escalation paths:

Hierarchical State Machine / Statechart — nested states share parent transitions, eliminating combinatorial duplication
Behavior Tree — composable tree of conditions and actions, well suited to reactive agents
Rule engine — declarative conflict-resolved rules over context
PDDL / HTN planning — when goal sequences are not known in advance

The right choice depends on whether the failure of FSM is structural (state explosion → HSM), expressive (cannot model composition → Behavior Tree), authorial (non-engineers must edit → rule engine), or generative (novel sequences required → planning).

Each escalation path is its own topic in this submodule.

XState as a Modeling Tool

XState is a JavaScript and TypeScript library that implements both FSMs and Statecharts.

A pure FSM definition contains only the model — no async, no orchestration:

import { createMachine } from 'xstate';

const triage = createMachine({
  id: 'triage',
  initial: 'ready',
  states: {
    ready: {
      on: { INPUT_RECEIVED: 'classifying' }
    },
    classifying: {
      on: {
        SIMPLE:  'classifiedSimple',
        COMPLEX: 'classifiedComplex',
        UNKNOWN: 'classifiedUnknown'
      }
    },
    classifiedSimple:  { type: 'final' },
    classifiedComplex: { type: 'final' },
    classifiedUnknown: { type: 'final' }
  }
});

The same library can drive durable orchestration with invoke, actors, and persistence — that surface area is covered in 1.1.1.

This note treats XState as a modeling tool only. The FSM is the same regardless of how it is run.

Cross-references

1.1.1 State machines in agentic systems — running an FSM in a distributed system: persistence, retries, idempotency, approval gates, tool authority.
Hierarchical State Machines (this submodule) — nested and concurrent states.
Behavior Trees (this submodule) — composable reactive behavior.
Goal-oriented planning, PDDL, HTN (this submodule) — generative planning over goals.
Rule engines (this submodule) — declarative behavior modeling.

References

Harel — Statecharts: A Visual Formalism for Complex Systems (1987)
Cassandras and Lafortune — Introduction to Discrete Event Systems
XState — stately.ai/docs/xstate
statelyai/xstate — github.com/statelyai/xstate