Divisible by three
A deterministic finite automaton with three states, one per possible remainder (0, 1 or 2) of the binary number read so far, modulo three. Reading a bit b in state r moves to state (2r + b) mod 3, because shifting a binary number one place left and adding a bit multiplies its value by two and adds that bit. The number is a multiple of three exactly when the machine ends in state q0.
When it is the right choice
As the module’s example of designing (or reading) a hand-built automaton directly as a language acceptor, which is a different skill from `/regex`’s own NFA and DFA pages: those derive their automaton from a pattern, by a construction algorithm. This one is simply asserted correct, the way a textbook presents it, and then checked.
How it works
- Start in state q0, which stands for "remainder 0 so far".
- Read the input one bit at a time, most significant bit first.
- In state r, reading bit b moves to state (2r + b) mod 3.
- After the last bit, the number is a multiple of three exactly when the machine is in q0.
Worth noticing
- No tape, no write, no leftward movement, no scratch alphabet — every one of the four things both Turing machines on this tool’s other pages depend on. This page is the clearest way to see what a tape actually buys a Turing machine over a DFA, by showing a task a DFA can still do without one.
- Every state has exactly one self-loop among its two outgoing rules (q0 on 0, q2 on 1) — a state that, on one particular symbol, stays exactly where it is. The state diagram draws this as a small loop rather than a line, because a line from a node to itself has no length to draw.
- The three scenarios land in each of the three possible states on purpose, so a reader sees all three possible verdicts rather than only the affirmative one.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)