import HtmlEmbed from '../../components/HtmlEmbed.astro';
import Wide from '../../components/Wide.astro';
import Note from '../../components/Note.astro';
import Sidenote from '../../components/Sidenote.astro';
import Accordion from '../../components/Accordion.astro';

# Building the Machine

Given a corpus of activity sequences, FSM construction is two steps and nothing else: build a prefix tree, then merge structurally equivalent states. There are no thresholds, no number of clusters, no learning rate.

## Step 1: Prefix Tree

Insert all activity sequences into a [trie](https://texonom.com/8b0d3da022e64279a5127e872536d7ca). Each unique prefix becomes a distinct state. The prefix tree has **perfect training fitness**, it replays every training trace exactly, but it can have tens of thousands of states.

For SWE-agent (2,000 traces), the prefix tree has **59,510 states**. Most are visited once and represent memorized suffixes rather than reusable transition patterns.

## Step 2: Structural Merging

Two states are *structurally equivalent* if for every activity $a \in \mathcal{A}$: (i) $\delta(q, a)$ is defined exactly when $\delta(q', a)$ is defined, and (ii) the targets are themselves equivalent. This recursion is computed bottom-up in a single pass.

<Note>
Structural equivalence is exactly the [Myhill-Nerode](https://texonom.com/ab9c3c96247d8389af2a8156427385b4) equivalence on the observed prefix language. By the Myhill-Nerode theorem the quotient is the **unique minimal [deterministic finite automaton (DFA)](https://texonom.com/f08438340ef447f89eade6aac52f2cbb)**, so no smaller automaton can reproduce the observed behavior [@hopcroft2006automata].
</Note>

The SWE-agent prefix tree with 59,510 states collapses to just **25 states**, a 2,380$\times$ compression, and the resulting FSM still replays held-out traces at 0.999 fitness.

<HtmlEmbed
  src="embeds/prefix-tree-collapse.html"
  title="Prefix Tree to FSM Collapse"
  caption="Watch a prefix tree collapse into a compact FSM through structural merging. States with identical outgoing transition patterns are merged iteratively until no further merge is possible."
/>

## The Resulting FSM

The FSM $\mathcal{M} = (Q, \mathcal{A}, \delta, q_0)$ encodes the agent's **behavioral topology**. Recurring patterns become loops, and the state count tracks the number of distinct behavioral modes.

In the tau2-bench retail and telecom customer service agents, a tool-call loop (`assistant:tool_call` to `tool:text`) dominates execution, with the conversational path through `assistant:text` as a separate branch. In a coding agent, the `search`, `edit`, `execute` cycle accounts for most of the trace.

<HtmlEmbed
  src="embeds/fsm-force-graph.html"
  title="Explorable FSM Graphs"
  caption="Select a dataset to explore its extracted FSM. Node size reflects visit frequency; edge thickness reflects transition frequency. Drag nodes to rearrange, scroll to zoom, drag the background to pan, and double-click to reset the view."
/>

Open the FSM explorer for any of the twelve datasets in the [live dashboard](https://seongland.com/article/asg/browser?tab=graph&dataset=sweagent).

## Theoretical Properties

The construction guarantees three properties.

**Fitness preservation.** Structural merging preserves training fitness: if a trace is accepted by the prefix tree, it is accepted by the merged FSM, because merging only adds out-edges (each state carries the union of its merged transitions).

**Compactness.** The merged FSM is a compact directly-follows automaton: one state per activity, deterministic, accepting every observed trace. We recover this, not the *generating* automaton, which is impossible to identify from positive examples alone [@gold1967language], but it is enough for faithful replay and prediction.

**Linear runtime.** Prefix tree construction is $O(\sum_i T_i)$, and structural merging is a partition refinement in $O(|Q_\mathcal{P}| \cdot |\mathcal{A}|)$. In practice all twelve datasets complete in under one second on a single CPU core.

<Note variant="info">
The construction itself is classical [@daciuk2000incremental]. What is new is that bounded agent alphabets make the resulting compact automaton small enough, and dense enough per state, to be useful for the prediction and monitoring tasks that follow.
</Note>