Finite State Machine

What is a finite state machine?

A formal FSM is defined by:

• A finite set of states Q.
• A finite alphabet Σ of input symbols.
• A transition function δ: Q × Σ → Q (for DFA) or Q × Σ → 2^Q (for NFA).
• An initial state q₀ ∈ Q.
• A set of accept states F ⊆ Q.

The machine starts in q₀, reads input symbols one at a time, and follows transitions. After consuming all input, if the current state is in F, the input is accepted. That's the entire model.

Example — match strings ending in "001"

           0          0          1
   ┌──── q0 ──────► q1 ──────► q2 ──────► q3 (accept)
   │  ▲              │           │           │
   1  │              1           1           0
   │  └──────────────┴───────────┘           │
   ▼                                          │
  q0 ◄────────────────────────────────────────┘
                       0 from any non-q3 state restarts

State meaning:
  q0 — haven't seen any prefix of '001'
  q1 — seen '0'
  q2 — seen '00'
  q3 — seen '001' (accept)

Four states, four input characters, transitions defined for each (state, input) pair. Linear in input length to simulate.

DFA vs NFA

	DFA	NFA
Active states at any moment	Exactly one	One or more
Transitions per (state, input)	Exactly one	Zero, one, or many
Epsilon transitions	No	Yes
Construction from regex	Hard (subset construction)	Easy (Thompson)
State count for same regex	Up to 2^n more	Linear in regex
Match speed	Faster (one state to track)	Slower (set of states to track)
Used in	Lexers (compile-time DFA)	Backtracking regex (runtime NFA)

Both recognize exactly the same languages — regular languages, by definition. The conversion between them is mechanical: subset construction (NFA→DFA) and the trivial inclusion (every DFA is an NFA).

Mealy vs Moore — output models

	Moore	Mealy
Output depends on	Current state only	Current state + input
State count for same behavior	Larger	Smaller
Easier to reason about	Yes — output is "where am I"	No — output couples to input
Hardware preference	Both common; Moore is glitch-free	Mealy more common in software
Examples	Traffic light (red/yellow/green is the state)	Parser emitting tokens (state + input → token)

When to use an FSM in code

• Network protocols. TCP has formal FSM states (CLOSED, LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT_1, ...). UDP doesn't have any state. Most protocols document their state machine explicitly.
• UI workflows. "User is editing → submitting → submitted" or "logged out → logging in → 2FA pending → logged in." XState is a popular JS library for FSM-driven UI.
• Lexers and parsers. Lexers are typically compiled to a DFA from regex rules. Parsers use stacks (pushdown automata) but the lexer underneath is pure FSM.
• Game AI. NPC behavior — idle, patrol, alert, attack, retreat — modeled as states with transitions on triggers. Hierarchical FSMs (HSMs) handle nested behaviors.
• Embedded systems. Microcontroller firmware almost always has an FSM at its core — power management, sensor reading cycle, motor control sequences.
• Validation rules. Email format, URL format, credit card number format — all regex, all FSM under the hood.

JavaScript: implementing an FSM

// Manual implementation
class TCPStateMachine {
  constructor() { this.state = 'CLOSED'; }

  transition(event) {
    const transitions = {
      CLOSED: {
        ACTIVE_OPEN:  'SYN_SENT',
        PASSIVE_OPEN: 'LISTEN',
      },
      LISTEN: {
        SYN_RECEIVED: 'SYN_RCVD',
        CLOSE:        'CLOSED',
      },
      SYN_SENT: {
        SYN_ACK:      'ESTABLISHED',  // simplified — real TCP also requires sending ACK
        CLOSE:        'CLOSED',
      },
      SYN_RCVD: {
        ACK:          'ESTABLISHED',
        CLOSE:        'FIN_WAIT_1',
      },
      ESTABLISHED: {
        CLOSE:        'FIN_WAIT_1',
        REMOTE_FIN:   'CLOSE_WAIT',
      },
      // ... etc
    };
    const next = transitions[this.state]?.[event];
    if (!next) throw new Error(`Invalid transition: ${event} from ${this.state}`);
    this.state = next;
    return this.state;
  }

  isConnected() { return this.state === 'ESTABLISHED'; }
}

// Using a library (XState style)
import { createMachine, interpret } from 'xstate';

const trafficLightMachine = createMachine({
  id: 'trafficLight',
  initial: 'red',
  states: {
    red:    { on: { TIMER: 'green' } },
    green:  { on: { TIMER: 'yellow' } },
    yellow: { on: { TIMER: 'red' } },
  },
});

const service = interpret(trafficLightMachine).start();
service.send('TIMER');  // red → green
service.send('TIMER');  // green → yellow
service.send('TIMER');  // yellow → red

Python: simple FSM with a dict

class FSM:
    def __init__(self, transitions, initial, accepts):
        self.transitions = transitions  # {(state, input): next_state}
        self.state = initial
        self.accepts = accepts

    def step(self, input_symbol):
        key = (self.state, input_symbol)
        if key not in self.transitions:
            raise ValueError(f"No transition from {self.state} on {input_symbol}")
        self.state = self.transitions[key]
        return self.state

    def accept(self, input_string):
        for c in input_string:
            self.step(c)
        return self.state in self.accepts

# Recognizer for strings ending in '001'
fsm = FSM(
    transitions={
        ('q0', '0'): 'q1', ('q0', '1'): 'q0',
        ('q1', '0'): 'q2', ('q1', '1'): 'q0',
        ('q2', '0'): 'q2', ('q2', '1'): 'q3',
        ('q3', '0'): 'q1', ('q3', '1'): 'q0',
    },
    initial='q0',
    accepts={'q3'},
)
print(fsm.accept('110001'))  # True

What FSMs cannot do

FSMs have constant memory — only the current state. Two famous things they can't do:

1. Match balanced parentheses. (((()))) requires counting opens minus closes. An FSM with k states can only count up to k. Push-down automata (FSMs with a stack) handle this — they recognize context-free languages.
2. Recognize palindromes of arbitrary length. Requires comparing positions far apart. An FSM has no memory of what it saw earlier.

The Chomsky hierarchy classifies these — regular (FSM) ⊂ context-free (PDA) ⊂ context-sensitive ⊂ recursively enumerable (Turing machine). Each level adds expressive power.

Hierarchical state machines

A regular FSM with 100 states is hard to read. Hierarchical FSMs (HSMs, statecharts — Harel 1987) nest states inside states. Common pattern — a "playing" superstate contains "running," "jumping," "swimming" substates. Events and transitions defined at the superstate apply to all substates (e.g., "PAUSE" works in any of the three).

HSMs reduce state count exponentially for complex behaviors. UML statecharts and IBM's Rhapsody are formal HSM tools; XState (JS) and SCXML (W3C) are widely-used implementations.

Common FSM bugs

• Implicit state via booleans. Three booleans (isLoggedIn, isLoading, hasError) represent 8 combinations, but only 4 are valid. The implicit FSM is buggy because invalid combinations are reachable. Make the states explicit.
• Missing transitions. Real systems have many event sources; forgetting to handle some events in some states leads to "stuck" or undefined behavior. List every state × event combination during design.
• Side effects in transitions vs entry actions. Mealy machines emit on transition; Moore machines emit on state entry. Mixing them produces hard-to-reason-about side effects (an action runs twice or zero times depending on the path). Pick one model and stick with it.
• Race conditions in concurrent FSMs. Two events arriving simultaneously at the same FSM cause non-deterministic state. Use single-threaded event loops, atomic state updates, or actor-model isolation.
• State explosion. A naive FSM for a complex system has too many states to fit on a whiteboard. Refactor into HSMs or compose multiple smaller FSMs (hierarchically or in parallel).
• Tight coupling between states and UI. The FSM should describe behavior; views should observe state changes. Mixing them produces fragile code. XState explicitly separates state machines from UI rendering.