Automata in Code: State Machines and Statecharts

Heartbleed (2014): an OpenSSL vulnerability that let an attacker read server memory. The cause was mishandled TLS heartbeat messages with no check on connection state. If TLS had been encoded as a strict FSM (as it is in rustls), a heartbeat in the wrong state would have been rejected at the type level. State machines are not theory, they are security.

• **rustls TLS library:** written in Rust, encodes TLS 1.3 as a type-safe FSM. Each state is a distinct type. You cannot call a method outside its valid state without a compile error. Used by Cloudflare, AWS, Firefox
• **XState and Stately:** statechart library for JavaScript. 10M+ downloads per week. Stately Studio is a visual editor for state machines. Microsoft Teams, Framer, Atlassian use XState for complex UI state
• **Erlang OTP gen_statem:** OTP behavior for encoding FSMs. Each process is an actor and an FSM. WhatsApp (Erlang), RabbitMQ, CockroachDB use gen_statem for protocol code
• **Unity Animator (mecanim):** a visual state machine for character animation. Each transition is a condition on parameters. Blend trees are hierarchical statecharts for smooth animation transitions

State Machines in Code

A **Finite State Machine (FSM)** in code is the direct realization of a DFA: a set of states, a current state, a transition table, and an output function. FSMs show up everywhere: the TCP stack, parsers, UI components, game NPCs, compilers. The main advantage is that behavior is explicit, transitions are predictable, and testability is high.

The alternative to an explicit FSM is **if/else spaghetti**: endless conditionals, global flags, opaque transitions. That is an anti-pattern usually called an 'implicit FSM'. An explicit FSM with a transition table makes adding a state into a single new row. Tests cover each transition independently.

Statecharts: Hierarchical Automata

**Statecharts** (Harel, 1987) extend FSMs with hierarchical states (nested), parallel states, and state history. XState (JavaScript) is the popular statechart implementation for UI. The problem with flat FSMs is state explosion: 10 parallel features means 2^10 states. Statecharts address this through hierarchy and parallelism.

**XState** is used in Stately Studio, Cloudflare Workers, and Microsoft Teams. **Erlang/Elixir gen_statem** is an FSM in the actor model. **Redux** implicitly implements an FSM: reducer is the transition function, action is the event. An explicit statechart in Redux Toolkit + XState is a popular architecture for complex UIs.

Automata for Protocol Validation

Network protocols (TCP, HTTP/2, TLS, WebSocket) are defined as state machines. A **TLS handshake** is a strictly defined sequence of states. Violating the order is an error or a vulnerability. Modern TLS stacks (rustls, BoringSSL) encode the protocol as an FSM and check every transition.

**rustls** (Rust TLS library) encodes the TLS 1.3 handshake as a strict FSM. Invalid transitions are impossible at the type level (state encoded in generics). This is the **type-safe State Pattern**: the compiler guarantees protocol correctness. Errors in TLS implementations (Heartbleed, BEAST) often come from incorrect state transitions.

Automata in Game AI and UI

**Behavior Trees** and **FSM** are the two main approaches to game AI. FSM: simple NPCs with a small set of states (patrol, alert, attack, flee). Behavior Trees: hierarchical decision making, widely used in AAA games (Halo, GTA). Unity Animator and Unreal Blueprints implement visual statecharts for NPCs.

**React components** implicitly form an FSM via useState. An explicit statechart with XState makes transitions predictable: no invalid states like (loading=true, error=true). **The Actor Model** (Erlang, Akka, XState): each actor is an FSM, interaction happens via messages. That is a scalable architecture for distributed systems.

Key Takeaways

• **FSM in code:** an explicit transition table beats implicit if/else. Adding a state means one new row, every transition is testable, invalid states are unreachable
• **Statecharts (Harel):** hierarchy + parallelism + history. They solve the state explosion of flat FSMs. XState is the popular UI implementation
• **Protocols as FSMs:** TCP, TLS, HTTP parsers. rustls encodes TLS state in types, giving compile-time protocol correctness
• **Game AI and UI:** NPC behavior via FSM or Behavior Trees. React components are implicit FSMs; explicit statecharts prevent invalid combinations

Related Topics

Automata in code are a direct application of finite automata theory:

• Deterministic Finite Automata — An FSM in code is the direct realization of a DFA: states, transitions, output function
• Regex in Practice — Regex engines are specialized FSMs for pattern matching
• Formal Verification — Model checking verifies FSM models of systems against temporal properties

Вопросы для размышления

• A Redux reducer is an FSM transition function. Which parts of Redux correspond to which parts of an FSM: states, events, transition function?
• Heartbleed was caused by a missing TLS state check. How does a type-safe FSM in rustls prevent that kind of vulnerability?
• Behavior Trees are more popular than FSMs for complex game AI. What are the limits of FSMs at scale, and how do Behavior Trees address them?

Связанные уроки

• comp-07-regex-in-lexer