FSM Fundamentals

Quick Cap

A finite state machine (FSM) is a model with a fixed set of states, a set of events (inputs) that can arrive, and transitions that move from one state to another in response to events. Actions are the side effects that happen on entry, exit, or during a transition. Every nontrivial firmware behavior — protocol parsers, button-debounce, BLE GAP, motor controllers — is a state machine; the only question is whether you make it explicit. Interviewers test FSMs because they reveal whether a candidate can structure complex behavior cleanly versus drowning in nested if/switch.

Key Facts:

• State = a "mode" the system is in, with a finite, well-named set
• Event = an external or internal trigger (button press, byte received, timer expiry)
• Transition = state change in response to an event, optionally guarded by a condition
• Action = side effect attached to entry, exit, or transition
• Mealy = output depends on (state, event); Moore = output depends only on state
• Determinism: from (current state, event), there is one next state and one set of actions

Deep Dive

At a Glance

What Is a State Machine, Really

An FSM is an explicit model of "what is the system doing right now, and how does that change in response to inputs?" Three pieces of information together define the FSM at any moment:

1. Current state — one of the named states
2. Event vocabulary — the set of events that can be delivered
3. Transition function — for each (state, event) pair, what's the next state and what actions fire

It's "finite" because the set of states and events is bounded — you can list them all on one page. This finiteness is what makes FSMs analyzable, testable, and (crucially) communicable: you can draw a state diagram and a coworker can understand the system at a glance.

Example: Button Debouncer

Imagine debouncing a momentary push-button. A naive implementation samples the pin and treats every change as a press — but mechanical bounce produces dozens of transitions per actual press. The clean FSM:

Four states (Released, PressWait, Pressed, RelWait); two events (PIN_CHANGED, TIMER_EXPIRED); transitions guarded by current pin level. Entry to Pressed fires the "send button-down event" action. Bounce noise that doesn't survive the debounce timer is silently rejected (the bounce transitions return to the prior stable state without emitting any event).

This is roughly 30 lines of clean code. The same logic in nested if/switch is 100 lines and impossible to verify by inspection.

States, Events, Transitions, Actions

The four pillars in detail:

States are nouns describing modes. Good state names are short, capital, and read naturally in transitions: IDLE, CONNECTING, READY_TO_TRANSMIT. Bad state names are verbs or vague: DOING_STUFF, WAIT_1, STATE_2. A state should mean something physically: "in this mode the radio is on, the LED is blue, and the only thing we're doing is waiting for an ACK."

Events are verbs describing what happened. Good events: BUTTON_PRESSED, BYTE_RECEIVED, LINK_DOWN. Bad events: EVENT_5, MISC_THING. Events have a clear source: hardware (interrupt), peer (incoming protocol byte), timer, application.

Transitions are the (state, event) → (next state, actions) tuples. A transition often has a guard — a Boolean condition that must hold. Without the guard, the transition does not fire even if the event arrives.

IDLE + BUTTON_PRESSED [battery_ok && config.enabled]  →  ACTIVE / start_motor()

Read as: "In IDLE, when BUTTON_PRESSED arrives, if battery_ok and config.enabled are both true, transition to ACTIVE and execute start_motor."

Actions are the side effects. Three flavors:

Entry and exit actions matter because they are invariants — they fire no matter how you enter or leave the state. Critical for safety: "every time we leave PUMPING, we MUST close the valve" → put close_valve() in the exit action. If you put it on each individual outgoing transition, a future engineer adding a new transition might forget.

Mealy vs Moore

Two formal models of FSM output:

In a Moore machine, the state alone determines the output. In LED_ON the LED is on; in LED_OFF the LED is off. Outputs change only on state transitions.

In a Mealy machine, outputs are attached to transitions, not states. The same state can produce different outputs depending on which event arrived. Mealy machines have fewer states for the same behavior but are harder to reason about because the output depends on the most recent event.

In practice, embedded FSMs are usually a hybrid: the state implies long-running behavior (Moore-style — "while in CONNECTED, the radio stays on"), and individual transitions can have additional one-shot actions (Mealy-style — "on the BYTE_RX event in PARSING_HEADER, latch the length field").

Entry / Exit / Transition Actions: Why the Distinction Matters

Consider a simple "garage door" FSM:

States:  CLOSED, OPENING, OPEN, CLOSING
Events:  BUTTON, OBSTACLE, FULLY_OPEN, FULLY_CLOSED

If safety requires "the obstruction sensor MUST be active whenever the door is moving," you put the sensor enable in the entry action of OPENING and CLOSING, and the disable in the exit action. Now no matter how a state is entered or left — by user button press, by limit switch, by obstacle detection — the sensor is correctly armed and disarmed.

Compare to "put the enable on every incoming transition" — works today, but six months later someone adds a EMERGENCY → CLOSING transition and forgets the enable. With entry actions, the invariant is structural; with transition actions, it depends on every coder remembering.

Why FSMs Beat Nested if/switch

Look at this code. What does it do?

if (mode == SETUP) {
    if (event == BUTTON && !battery_low) {
        mode = ACTIVE;
        led_on();
        if (autostart) start_motor();
    } else if (event == TIMEOUT) {
        // ... 30 more lines
    }
} else if (mode == ACTIVE) {
    if (event == BUTTON) {
        if (battery_low) {
            mode = ERROR;
            error_blink();
        } else {
            mode = PAUSED;
            led_dim();
        }
    }
    // ... more
}

Now imagine 8 modes and 12 events. The behavior is buried in conditional structure, not visible at a glance. Coverage testing requires hand-tracing every nested branch. Adding a new state means hunting through the file for every place that checks mode.

The same logic as an explicit FSM with a transition table:

The behavior is data, not code structure. You can:

• Read it as a table — coverage is "every row hit at least once"
• Generate code from it — table-driven FSM (next topic)
• Generate test cases from it — fuzz the (state, event) cross product
• Visualize it — auto-generate a state diagram

Visualizing as a State Diagram

A state diagram (the standard UML notation) draws states as rounded rectangles and transitions as arrows labeled event [guard] / action. Mermaid handles this directly:

When designing or reviewing an FSM, draw the diagram first. If the diagram looks like a hairball, the FSM is poorly factored — split it into separate concerns (often a sign that you need a hierarchical FSM, covered in Hierarchical State Machines).

Determinism and Total Specification

Two desirable FSM properties:

• Deterministic: For any (state, event) pair, there's at most one matching transition. If two transitions both match (same state, same event, both guards true), the FSM is non-deterministic — almost always a bug.
• Totally specified: Every (state, event) pair is handled — even if the handler is "do nothing, stay in current state." This forces you to think about every event in every state. Common pattern: a default DROP_EVENT action for unexpected combinations.

A practical embedded FSM often has a "trap" handler for (any state, unexpected event) that logs the event and either ignores or asserts. This catches "I didn't think about that case" bugs as soon as they happen rather than silently misbehaving.

When NOT to Use an Explicit FSM

FSMs are not free — they add structure overhead and learning curve. Skip them when:

• The behavior really is "do this every loop iteration" with no modes (a simple polling loop)
• There are only 2 states and 1-2 transitions (a flag suffices)
• The "states" are actually data values, not modes (e.g., counter values)

If you find yourself defining 8 enum values and writing if (mode == X) { ... } else if (mode == Y) { ... }, you have an FSM whether you wanted one or not. Make it explicit.

Debugging Story: The Mystery LED

A team's wearable's LED would occasionally get stuck on after disconnect. After hours of bisecting commits, the bug was traced to a transition that turned the LED off as a side effect — but only on the "user pressed disconnect" path. The "BLE link lost" path also exited the connected state, but didn't turn the LED off. Two transitions exiting the same state, two implementations of the same invariant, one of them buggy.

The fix was structural: move LED-off into the exit action of CONNECTED. Now both transitions out automatically turn the LED off, plus any future transitions added later. Plus the test plan is simpler: "on entry to any non-CONNECTED state from CONNECTED, LED is off" — one assertion instead of N (one per outgoing transition).

The lesson: Invariants belong in entry/exit actions, not duplicated across transitions. The bug rate scales with the number of places the invariant is restated.

What Interviewers Want to Hear

• You can name the four FSM concepts (state, event, transition, action) crisply
• You can distinguish entry/exit/transition actions and explain when each is appropriate
• You can compare Mealy and Moore and pick one for a given scenario
• You can articulate why explicit FSMs beat nested if/switch
• You can draw a state diagram for a simple behavior
• You know about determinism and total-specification as design properties

Interview Focus

Classic Interview Questions

Q1: "What is a finite state machine, and what are its components?"

Model Answer Starter: "A finite state machine is an explicit model of system behavior with four parts. States are the named modes the system can be in — IDLE, CONNECTED, CHARGING for example. Events are the inputs that can trigger changes — button presses, incoming bytes, timer expiries. Transitions are (current state, event) → (next state) arrows, often with guards (Boolean conditions). Actions are side effects that fire on entry to a state, exit from a state, or during a specific transition. The 'finite' part is that the states and events are a bounded set you can list on one page — that's what makes FSMs analyzable and testable."

Q2: "Mealy vs Moore — which is more common in embedded firmware?"

Model Answer Starter: "Moore-style is more common because most embedded behavior is mode-driven: in CONNECTED the radio is on regardless of what event arrived; in IDLE it's off. The state determines the long-running output. Mealy-style is useful for protocol parsers and similar code where the same state produces different outputs based on which event arrived — for example, a UART parser in WAITING_FOR_PAYLOAD_BYTE does different things on BYTE_RX(0x7E) (end-of-frame) versus BYTE_RX(other) (accumulate). In practice most firmware FSMs are hybrids: state implies long-running behavior (Moore) and individual transitions can carry one-shot actions (Mealy)."

Q3: "When would you choose an entry action over a transition action?"

Model Answer Starter: "Entry actions fire every time the state is entered, regardless of which transition led there. Transition actions fire only on one specific transition. So entry actions are for invariants — things that must be true whenever you're in this state. If safety requires 'whenever the motor is running, the brake is released', put 'release brake' in the entry action of MOTOR_RUNNING. That way, no matter how you got there — startup, recovery from fault, manual override — the brake is released. Putting it on each individual incoming transition risks a future transition forgetting it. Same logic for exit actions: anything that must be true on leaving this state."

Q4: "Show me a concrete case where an explicit FSM is much cleaner than nested if/switch."

Model Answer Starter: "Take a button debouncer. The naive nested-if version reads the pin, checks elapsed time, checks 'last state', and produces button-down events through a tangle of conditions — usually 50+ lines that are hard to reason about. As an explicit FSM with four states (RELEASED, PRESSED_DEBOUNCE, PRESSED, RELEASED_DEBOUNCE), two events (PIN_CHANGED, TIMER_EXPIRED), and a transition table, the same behavior is 30 lines, the bounce-rejection logic is structural rather than buried in conditions, and you can test it by injecting events into a transition function. The FSM also makes it obvious what the 'real' button events are — entry to PRESSED is the canonical button-down moment."

Q5: "What does it mean for an FSM to be deterministic and totally specified, and why does it matter?"

Model Answer Starter: "Deterministic means for any (current state, event) pair, there's at most one matching transition. If two transitions both match — same state, same event, both guards true — the behavior is undefined and almost always a bug. Totally specified means every (state, event) pair has a defined handler, even if the handler is 'do nothing, stay here'. It matters because it forces you to think about every event in every state during design. A common practical pattern is a default trap handler for unexpected (state, event) combinations that logs the event for diagnostics — catches 'I didn't think about that case' bugs as soon as they happen instead of silent misbehavior."

Trap Alerts

• Don't say: "I'd just use a flag" — for anything past 2-3 states, that's an FSM in disguise; make it explicit
• Don't forget: Entry/exit actions for safety invariants — the "do this when leaving this state" guarantee is structural
• Don't ignore: Unexpected (state, event) combinations — total specification + a trap handler catches design oversights

Follow-up Questions

• "How would you sketch a TCP connection FSM?"
• "What's the difference between an FSM and a flowchart?"
• "How do you handle timers as events in an FSM?"
• "Can two FSMs in the same firmware run in parallel safely?"
• "When would you use multiple FSMs vs one big one?"
• "What's the relationship between state machines and statecharts?"

Practice

Real-World Tie-In

BLE GAP State Machine — A Bluetooth peripheral's GAP layer is naturally an FSM with states like STANDBY, ADVERTISING, CONNECTED, DISCONNECTING. Events arrive from the controller (CONN_REQ_RECEIVED, LINK_LOST, DISCONNECT_COMPLETE) and from the application (START_ADV, DISCONNECT). Drawing the GAP FSM as a state diagram makes the protocol's behavior obvious and lets reviewers verify safety properties (e.g., "we never advertise while connected").

Motor Controller Mode Manager — Industrial motor drives use FSMs with states like INIT, IDLE, STARTING, RUNNING, BRAKING, FAULT. Entry to FAULT engages the brake (entry action) and disables PWM outputs; exit from RUNNING ramps PWM down (exit action). Safety inspectors trace every path through the FSM looking for ways to leave RUNNING without going through brake-ramp-down — entry/exit actions make this audit straightforward.

TCP Connection FSM — RFC 9293 specifies TCP behavior as an explicit state machine: CLOSED, LISTEN, SYN_SENT, SYN_RCVD, ESTABLISHED, ... TIME_WAIT, CLOSED. Every TCP implementation reproduces this FSM. Bugs in implementations are typically traced by recording the state sequence and comparing to the spec; non-conforming transitions are easy to spot when behavior is encoded as data.