Finite-state machine (sequence recognizer)
A three-state machine reads a binary string bit by bit and decides whether its value is a multiple of 3, without ever storing the number.
A finite-state machine has only finitely many states, and on each input symbol it moves from one state to
another by its transition table δ. If it ends in an accepting state, the string is accepted.
- Time:
O(n) - Space:
O(1) - Johnsonbaugh, chapter 12
- Grimaldi, chapter 6
10010 = 18 is a multiple of 3; the machine ends in state 0.
def multiple_of_three(s):# A machine with three states: the value read so far, mod 3. Reading bit b turns value v into 2v + b.delta = {0: {"0": 0, "1": 1}, 1: {"0": 2, "1": 0}, 2: {"0": 1, "1": 2}}table = [[q, delta[q]["0"], delta[q]["1"]] for q in range(3)] # rows: state, after 0, after 1state = 0for i in range(len(s)):state = delta[state][s[i]]accepted = state == 0return accepted
Start
The table is still empty.
Local variables
Orange = changed in this step
Call stack
- multiple_of_three()line 1
Explanation
The idea
A finite-state machine has only finitely many states, and on each input symbol it moves from one state to
another by its transition table δ. If it ends in an accepting state, the string is accepted.
Three states are enough
If the bits read so far have value v, reading bit b makes it 2v + b. For divisibility by 3 only v mod 3
matters:
v mod 3 = r ⇒ (2v + b) mod 3 = (2r + b) mod 3
So the three states 0, 1 and 2 suffice, however big the number. State 0 is both the start and the accepting
state.
What to watch in the trace
- The table is the machine's transitions (one row per state); the
statecard follows each bit read.