Finite State Machines and What They Recognise
A machine with a fixed set of states that moves between them as it reads one input symbol at a time, drawn as a state transition diagram or written as a table. It has no memory beyond the state it is in, which fixes what it can and cannot recognise.
What a learner can do afterwards
- Represent a deterministic string recogniser as a state transition diagram and matching table
- Decide whether a given input string is accepted by a machine
- Explain why recognising balanced parentheses at arbitrary nesting depth needs more than finitely many states
1 · Read
Here we use a deterministic finite-state recogniser. It has finitely many states, an input alphabet, transition rules, a start state and accepting states. Each combination of a state and an input symbol determines one next state. It reads one symbol at a time. Its current state is all its working memory. That state can summarise earlier input without storing the whole history.
To recognise binary strings ending in 01, start in A. B means the current string ends in 0. C means it ends in 01; only C accepts. A covers all other cases, including empty input. The rows below give the next state for input 0 and input 1. These are three suffix categories, not a record of every possible pair of final symbols.
Draw each state as a circle and each transition as an arrow labelled with its input. Mark the start with an incoming arrow and accepting states with double circles. An arrow from A to B labelled 0 becomes the table entry: current state A, input 0, next state B. Record every transition and preserve the start and accepting states. To test a string, read all symbols before checking acceptance. Empty input leaves the machine at its start state.
Balanced parentheses have matching openings and closings, with no early closing. A machine with n states reads the n+1 prefixes containing zero through n openings. Two different depths must reach the same state. Add enough closings to balance the shallower depth. The deeper one stays unbalanced, but both runs now follow identical transitions from the same state. They cannot get different acceptance decisions. No fixed finite set of states handles every nesting depth.
Fixed states, one symbol at a time, and the landing state decides.
Lesson, questions and flashcards on finite-state recognisers written for this dataset.
Additional readings and flashcards on finite-state recognisers written for this dataset.
More to read
Specifying a recogniser
Before tracing any input, specify the states, input alphabet, transitions, start state and accepting states. For a deterministic recogniser, each state and input symbol selects one next state.
Acceptance is checked after the entire input has been read. Passing through an accepting state earlier does not settle the result. A later symbol may move the machine elsewhere.
Empty input makes no moves. It is accepted exactly when the start state is accepting.
Matching arrows and entries
An arrow from P to Q labelled 1 becomes a table entry with current state P, input 1 and next state Q. An arrow returning to P becomes an entry whose current and next states are both P.
To build a diagram from a table, draw the state circles first. Add one labelled arrow for each transition entry. Carry over the start and accepting markings.
Check all entries against their arrows. Agreement on one sample string alone does not show that two complete machines are equivalent.
Different histories, one state
A recogniser for strings ending in 01 can merge many input histories. The strings 10 and 1110 differ, yet both end in 0. Appending 1 makes either string end in 01; appending 0 leaves either ending in 0.
The state therefore needs a useful suffix category, not a copy of either complete history. This is how finite memory can retain information about earlier input while forgetting details that do not affect future acceptance.
A fixed nesting limit
A fixed maximum depth changes the parentheses task. For a depth limit of two, use states for zero, one and two unmatched openings, plus a rejecting state.
An opening increases the count unless it would exceed two. A closing decreases it unless it would go below zero. Either invalid move enters the rejecting state, which cannot be left. At the end, accept only count zero.
This machine accepts balanced strings within the chosen depth limit. It does not recognise all balanced-parentheses strings, because some valid strings nest more deeply.
2 · Watch
En anglaisTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.