Finite State Machines
Finite state machines
A finite state machine (FSM) is an abstract model of computation with a finite number of states. At any moment it is in exactly one state, and inputs cause transitions from one state to another. FSMs describe systems whose behaviour depends on their current state — traffic lights, vending machines, lexical analysers, protocols.
Key parts
- A set of states, drawn as circles.
- A start state (arrow pointing in from nowhere).
- Transitions — arrows labelled with the input that triggers them.
- For some FSMs, one or more accepting (final) states, drawn as a double circle.
Two types
- Finite State Automaton (FSA): has accepting states and is used to recognise whether an input string is valid (accepted) or not. Given an input, follow the transitions from the start state; if you end in an accepting state, the string is accepted.
- Mealy / general FSM with output: each transition can also produce an output (used to model machines that do something, not just accept/reject).
State transition diagrams and tables
The same FSM can be shown as a diagram (states + labelled arrows) or a state transition table:
| Current state | Input | Next state |
|---|---|---|
| S0 | 1 | S1 |
| S1 | 0 | S1 |
| S1 | 1 | S2 (accept) |
FSMs and regular languages
FSMs are equivalent in power to regular expressions — any language that can be described by a regular expression can be recognised by an FSM, and vice versa. This is why FSMs are used in the lexical analysis stage of compilers to recognise tokens (identifiers, numbers, keywords).
Limits
An FSM has no memory beyond its current state (it can't count arbitrarily), so it cannot recognise everything — e.g. checking perfectly balanced brackets of any depth needs more than a finite state machine (that requires a stack / pushdown automaton).
Worked example
An FSA accepts binary strings ending in "1". Starting in S0, describe acceptance of "101".
- Read 1 → go to accept state; read 0 → leave accept state; read 1 → return to accept state. Ends accepting → "101" is accepted (it ends in 1). ✓
Common mistakes
- Forgetting to mark accepting states (double circle) when recognition is required.
- Trying to trace an input from the wrong (not the start) state.
- Claiming an FSM can count/match unlimited brackets — it has no memory.
Exam tips
- Be able to convert between a state transition diagram and a table.
- Trace an input string and state whether it ends in an accepting state.
- Link FSMs to regular expressions and lexical analysis.
Key facts to remember
- An FSM has finite states, a start state, and transitions triggered by inputs; FSAs also have accepting states.
- Represent as a state transition diagram or table; FSMs recognise exactly the regular languages (equivalent to regular expressions).
- FSMs have no memory beyond the current state, so they can't handle unbounded counting/matching.