skip to content

How many states does a deterministic finite acceptor need for a stated digit rule, and how do you know?

level: seniorimportance: nice to knowfreq 30%

answer

  1. count situations, not symbols
  2. what must survive into the future
  3. one state per distinct summary
  4. windows multiply, remainders do not
  5. plus a trap and a start state

basics

~20 s

Count the situations the machine must tell apart, because each one is a state. A remainder rule needs one state per remainder, a parity rule two, a fixed pattern of length k needs k plus one, and a window of the last k symbols needs about s to the power k.

solid answer

~50 s

Do the counting before you draw anything: list what the machine must carry forward, and one state per distinct value of that is your answer. Divisibility by `m` needs `m` remainder states; an even-count rule needs two; "contains a pattern of length `k`" needs `k + 1`; remembering the last `k` symbols over an alphabet of size `s` needs on the order of `s` to the power `k`, which is where tables explode. Add one non-accepting trap if the input alphabet is wider than the rule allows, and one extra start state if the empty string must be rejected. The count matters because the implementation is a table of states times symbols, and on a fixed-function device that table is the budget. If what must be remembered grows without limit as the input grows, no fixed number of states is enough at all.

go deeper

for a junior

Know that each state stands for a distinct situation the machine must tell apart, and that the number of them is fixed before any input arrives.

for a middle

Do the counting out loud for a stated rule: name what must be remembered, count its distinct values, then add the trap and any separate start state.

for a senior

Turn the count into a budget. States times alphabet is the table, the register width follows from the state count, and a rule that needs a wide window may be worth renegotiating.

for a principal

Own the trade between rule expressiveness and device cost: choosing a rule whose summary is bounded and small is a design decision made before implementation, not a detail discovered during it.

## One state per situation you must tell apart The question "how many states?" is really "how many situations does the machine need to distinguish?" Two prefixes may share a state exactly when no continuation could ever separate their verdicts. So the counting procedure is: 1. Write down, in words, what the machine must know after reading an arbitrary prefix in order to finish the job. 2. Count the distinct values that description can take. 3. Add the housekeeping states: a trap if the alphabet is wider than the rule, an extra start state if the empty string must be handled differently. Step 1 is the one that takes thought, and it is also the one an interviewer is grading. ## Worked counts | rule over digits | what must be remembered | states | |---|---|---| | value divisible by `m`, read most significant first | the remainder of the value so far | `m` | | an even number of one chosen symbol | one parity bit | 2 | | contains a fixed pattern of length `k` | how much of the pattern ends the input so far | `k + 1` | | the last `k` symbols, over an alphabet of size `s` | the window itself | about `s` to the power `k` | | any symbol outside the rule's alphabet | nothing beyond "already invalid" | one trap | The fourth row is the one that bites. Remembering the last three decimal digits means one state per ordered triple: **1000** of them, plus a handful of start-up states for the stretch before three digits have arrived. Widen to four digits and it is 10,000. Nothing is wrong with the model; the memory is still constant in the length of the input, but constant can be large, and it grows exponentially in the width of the window. ## The table is the cost An implementation is a lookup table with **states times alphabet symbols** entries, plus a register wide enough to name a state: - 3 remainder states over 10 digits: 30 entries, and 2 bits of state. - 1000 window states over 10 digits: 10,000 entries, and 10 bits of state. On a fixed-function validator with no buffer, that table is the whole design budget, which is why the counting step happens before any drawing. It is also why a rule is sometimes rewritten rather than implemented: a rule that needs a wide window is often replaceable by one that needs a residue or a parity bit, at no loss to what the device is actually checking. ## When no finite count works Some rules have no answer at all to the counting question, because the description in step 1 takes unboundedly many values — "how many more of this symbol than that one have I seen", or "how deep am I inside a nesting". Whatever bound you pick, an input long enough defeats it, so there is no finite state set. Recognising this early saves you from drawing a machine that cannot exist; the formal argument for such a claim is a separate subject, and the practical move is to notice that your description of what must be remembered has no ceiling. The reverse mistake is just as costly: assuming a rule needs unbounded memory because the *input* is unbounded. The input's length is irrelevant. Divisibility works over a stream of any length in a fixed number of states, because the summary is bounded even though the string is not. ## How to check your count - **Name each state in words.** If you cannot say what a state means without referring to the input's position or length, the description is not bounded and the count is wrong. - **Look for two states that always behave the same.** If every symbol takes both to the same place and both agree on accepting, you have written the same situation twice. - **Check the housekeeping.** A trap and a distinct start state are easy to forget and each changes the count by one. - **Sanity-check the exponent.** Window rules multiply, so an alphabet of `s` symbols and a window of `k` gives `s` to the power `k`, not `s` times `k`; getting this backwards understates a table by orders of magnitude. ## Where candidates go wrong - Counting states per input symbol or per position, which cannot be finite. - Assuming more states means a better machine; the count is a cost, not a quality. - Reporting the alphabet size as the state count, which confuses the table's width with its height. - Believing any rule expressible in words has a finite-state machine behind it.

  • Why does remembering the last three digits cost so much more than remembering a remainder?
    Because the window keeps the digits themselves, so every ordered triple is a separate situation: ten choices three times over, about a thousand states. A remainder throws the digits away and keeps only their combined effect, which has as many values as the divisor. Discarding detail is what keeps the count small.
  • Does a longer input ever force a machine to have more states?
    No. The state count is fixed before any input is seen, and a correct machine runs over a stream of any length in that same fixed space. What forces more states is a richer thing to remember, not a longer string, which is exactly why these validators suit devices with no buffer.
  • What is the first sign that a rule cannot be done with a fixed number of states?
    Your own description of what must be remembered has no ceiling — it mentions a count with no bound, or a depth that the input may grow at will. If naming the states requires a quantity that increases with input length, no finite state set can hold them.

saying these in an interview costs you the question

  • Counts one state per symbol position in the input
  • Says a longer input needs a machine with more states
  • Quotes the alphabet size as the number of states
  • Multiplies window length by alphabet size instead of exponentiating
  • Assumes every rule you can state in words has a finite-state machine
  • Treats a bigger state count as a sign of a better design