skip to content

How would you design a deterministic finite acceptor that accepts exactly the digit strings divisible by three?

level: middleimportance: should knowfreq 48%

answer

  1. remember the least you can
  2. digits are gone once counted
  3. one state per remainder class
  4. appending a digit multiplies by ten
  5. ten leaves remainder one here

basics

~20 s

Make each state a remainder. Three states hold the value-so-far modulo three; reading digit d in remainder r moves to (10r + d) mod 3, which simplifies to (r + d) mod 3. Remainder zero is the accepting state.

solid answer

~40 s

Start from the question "what is the least I must remember?" — not the digits seen, only the value so far **modulo three**. That gives three states, `R0`, `R1` and `R2`. Reading digit `d` in state `Rr` appends a digit, so the value becomes `10r + d`, and the next state is `R[(10r + d) mod 3]`; because ten leaves remainder one when divided by three, that is the same as `R[(r + d) mod 3]`. `R0` is the accepting state. If the empty string must be rejected, add a separate non-accepting start state whose transitions mirror `R0`'s, giving four states. Finally make the machine total: any symbol that is not a digit goes to a non-accepting trap. The whole validator is then a table and one register, with no buffer at all.

code

pseudocode · 17 lines
pseudocode
# states: START (not accepting), R0 (accepting), R1, R2, TRAP (not accepting)
# value so far, modulo 3, is the only thing remembered

state = START

for each symbol s in input:
    if s is not one of 0..9:
        state = TRAP                       # absorbs everything after it
    else if state == TRAP:
        state = TRAP                       # no way out, by construction
    else if state == START:
        state = R[ value(s) mod 3 ]        # first digit: remainder is the digit
    else:
        r = index(state)                   # 0, 1 or 2
        state = R[ (10 * r + value(s)) mod 3 ]

accept if state == R0

go deeper

for a junior

Recall the shape of the answer: the states are the possible remainders, and the accepting state is remainder zero. Being able to trace a short digit string through it is enough at this stage.

for a middle

Derive the transition yourself from appending a digit, (10r + d) mod m, and say why it collapses to (r + d) mod 3 for this divisor. Handle the empty string and the non-digit symbol explicitly.

for a senior

Show the design judgement: constant memory and one pass on a device with no buffer, no early rejection available because no residue state is absorbing, and a table sized by divisor times alphabet.

for a principal

Weigh the recogniser against alternatives for the device: a fixed table is predictable in space and time and easy to certify, whereas anything that accumulates a value inherits width limits and overflow questions.

## Choose the states from what must be remembered The design step that matters is not drawing circles, it is deciding **what the machine has to carry forward**. For divisibility, the digits themselves are irrelevant once their effect on the remainder is known: two prefixes with the same remainder behave identically for every possible continuation. So the state set is the set of remainders. - Divisor three gives **three states**: `R0`, `R1`, `R2`. - `R0` is the **accepting** state — remainder zero means divisible. - The start state is the remainder of the empty prefix, which is zero. That is the entire memory: two bits, regardless of how long the code is. A handheld reader can validate a thousand-digit stream in the same space it validates a three-digit one. ## The transition rule Appending digit `d` to a number whose value is `v` produces `10v + d`. Remainders respect that arithmetic, so from remainder `r` the next remainder is `(10r + d) mod 3`. Because `10 mod 3 = 1`, the factor of ten disappears and the rule collapses to `(r + d) mod 3` — which is the familiar schoolroom fact that a decimal number is divisible by three exactly when its digit sum is. | state | digit 0, 3, 6, 9 | digit 1, 4, 7 | digit 2, 5, 8 | |---|---|---|---| | `R0` (accepting) | `R0` | `R1` | `R2` | | `R1` | `R1` | `R2` | `R0` | | `R2` | `R2` | `R0` | `R1` | Trace `1 0 2`: `R0` → `R1` → `R1` → `R0`, so it is accepted, and indeed 102 = 3 x 34. Trace `1 0 1`: `R0` → `R1` → `R1` → `R2`, rejected, and 101 is not a multiple of three. ## Start state, accepting state and the empty string Because the start state is `R0` and `R0` accepts, the machine as described **accepts the empty string**. That is mathematically tidy and usually wrong for a scanner, which should not treat "no digits at all" as a valid code. Two clean fixes: 1. Add a distinct non-accepting start state `S` whose outgoing transitions copy `R0`'s, so the first digit moves into the residue states and can never return to `S`. Four states. 2. Keep three states and reject empty input outside the machine, in the caller. Option 1 keeps the language exactly right and is the answer an interviewer is looking for; option 2 is a note about where you put the check. ## Making the machine total The scanner's alphabet is wider than the ten digits: the sensor may emit a symbol that is not a digit at all. Every such pair needs a successor, so route them all to one non-accepting **trap** that loops to itself on everything. A string containing any non-digit therefore ends non-accepting whatever follows it. ## Other divisors, and reading the other way The construction generalises directly: for divisor `m`, use `m` states and the rule `(10r + d) mod m`. What does **not** generalise is the simplification — `10 mod 7 = 3`, so a divisibility-by-seven machine needs the full `(10r + d) mod 7` and its table shows no digit-sum shortcut. Keep the general form and simplify only when you have checked the arithmetic. One more assumption is worth saying aloud: this machine reads **most significant digit first**, which is what appending a digit means. A machine fed the digits in the other order needs a different construction in general, because each digit's contribution depends on its position. Divisibility by three is the lucky case where it does not matter, since every power of ten leaves remainder one. ## Checks before you trust it - Trace at least one accepted and one rejected string end to end, and verify the verdict against actual arithmetic. - Confirm the number of states equals the divisor, plus the start state if empty input must be rejected, plus the trap. - Confirm exactly one state is accepting; a second accepting residue would accept numbers that are not multiples. - Confirm the table has one entry for every state-and-symbol pair before you call the machine deterministic.

  • How does the design change for divisibility by seven?
    Seven states, one per remainder, with the transition `(10r + d) mod 7`. The shortcut used for three does not carry over, because ten leaves remainder three rather than one when divided by seven, so there is no digit-sum rule to lean on and the table must be computed entry by entry.
  • Why does the machine not need to remember the digits it has read?
    Because any two prefixes with the same remainder lead to the same verdict for every possible continuation: the next remainder depends only on the current one and the incoming digit. Anything the machine cannot use to distinguish futures is not worth storing, which is what keeps the memory constant.
  • What breaks if the machine starts in the accepting remainder-zero state?
    It accepts the empty input, since the verdict with no symbols read is taken from the start state. For a code validator that is a false accept. Adding a non-accepting start state that copies remainder zero's outgoing transitions fixes it without changing any other string's verdict.

saying these in an interview costs you the question

  • Uses one state per digit value rather than per remainder
  • Tries to accumulate the whole numeric value in the state
  • Applies the digit-sum shortcut to divisors where it does not hold
  • Forgets that starting in remainder zero accepts the empty string
  • Leaves non-digit symbols with no transition at all