skip to content

Why must a deterministic finite acceptor define a transition for every state and symbol, including invalid ones?

level: middleimportance: must knowfreq 55%

answer

  1. a function is defined everywhere
  2. a run never gets stuck
  3. rejection is a place, not a stall
  4. one sink swallows the rest
  5. non-accepting, self-loop on every symbol

basics

~20 s

Determinism means exactly one successor for every state-and-symbol pair, so the transition rule must be total and no run can ever get stuck. Symbols a rule forbids are usually routed to a non-accepting trap state that absorbs the rest of the input.

solid answer

~40 s

Determinism is a claim about totality as much as about single-valuedness: for every state and every symbol of the alphabet there is one and only one successor, so a run always has somewhere to go and always consumes the whole input. That is what makes rejection a *state* rather than a failure to move. The usual way to meet the requirement for input the rule forbids — a symbol outside the accepted format, a character where a digit belongs — is a **trap state**: non-accepting, with every symbol looping back into it. Once the run falls in, it can never leave, so the verdict is fixed from that point on. Diagrams normally omit the trap and its arrows for readability; a machine drawn with missing arrows is shorthand for one that has it.

go deeper

for a junior

Remember that the transition rule covers every state and every symbol, so a run always has a move and always finishes. Bad input goes somewhere rather than stopping the machine.

for a middle

Explain totality as part of what determinism means, and construct the trap yourself: one non-accepting state, every symbol looping back, reached from every undefined pair.

for a senior

Bring it to a real streaming validator: identify which states are absorbing, and use that to say exactly where an early reject is safe and where the machine must read to the last symbol.

for a principal

Treat completion as an interface decision. Accepting a wider alphabet and trapping the rest keeps the recogniser total and the error handling in one place, rather than spreading input validation across the callers.

## Determinism is a totality claim The transition rule of a deterministic finite acceptor is a **function from (state, symbol) to state**, and a function is defined on its whole domain. Two separate requirements hide in that one sentence: - **Single-valued** — never two successors for one pair. This is what stops the run from branching. - **Total** — never zero successors either. This is what stops the run from halting in the middle of the input. The second is the one candidates forget. Its consequence is structural: **a run can never get stuck**, so "the machine had nowhere to go" is not a possible outcome. Rejection is something you *end in*, not something you *fail into*. ## The trap state When the alphabet is wider than the rule allows — the scanner's alphabet includes every symbol the sensor can emit, but the checksum rule only accepts digits — you still owe a successor for the disallowed symbols. The standard answer is a single **trap state** (also called a dead or sink state) with two properties: 1. It is **not accepting**. 2. **Every symbol** maps it back to itself, so it absorbs the remainder of the input. That is enough to make the whole machine total while preserving the intended language: any string with a forbidden symbol anywhere in it lands in the trap and stays there, so it ends non-accepting no matter what follows. A trap is the usual way to reach totality, not the only way — a rule that genuinely tolerates a symbol can name a real state for it instead. ## Why drawings leave it out A machine over ten digit symbols with five states has fifty entries in its table; drawing fifty arrows is unreadable, so the convention is to draw only the interesting ones and let the reader supply the trap. | what you see | what it means | what to ask | |---|---|---| | every state has an arrow for every symbol | the machine as defined | nothing; trace it as drawn | | some arrows missing | shorthand for a trap-completed machine | is the implied sink non-accepting? | | a state with a self-loop on every symbol, not accepting | the trap drawn explicitly | which symbols reach it, and from where? | When you are asked to "complete" a machine in an interview, this is the exercise: add one non-accepting state, route every undefined pair to it, and loop it to itself on everything. ## What this looks like in a streaming validator A fixed-function reader that validates a code digit by digit has no buffer to fall back on, so the trap is not an abstraction — it is the error latch. Two practical points follow: - **Fixing the verdict early is allowed; skipping the input is a separate decision.** Once the run is in an absorbing state, no later symbol can change the accept status, so the device may light the reject indicator immediately. The model still defines the run over the entire string; stopping early is an implementation choice that must not change which strings are accepted. - **Not every rule permits early rejection.** A machine whose states are residues of a divisibility rule has no absorbing non-accepting state at all: from any residue, some suffix still leads to acceptance. Such a validator must read to the last symbol before it can say anything. Knowing which of your states are absorbing tells you exactly where an early exit is safe. ## Totality is not correctness A total transition rule guarantees only that the machine always has a move. It says nothing about whether the machine accepts the right language, and nothing about whether it accepts a lot or a little — a total machine with an empty accepting set rejects every string, including the empty one. Totality is a well-formedness property of the definition, in the same family as "the start state is in the state set". ## Where candidates go wrong - Treating a missing arrow as "reject and stop" rather than as a trap, which quietly changes what the machine does on a *prefix* that is fine so far. - Making the trap accepting so it can "report the error", which inverts the verdict for every malformed input. - Adding a separate trap per error cause. One suffices for membership, because the language only asks yes or no; per-cause diagnostics are a reporting concern layered on top of the acceptor, not part of it. - Assuming every state needs its own escape hatch, when the trap can be reached from anywhere and left from nowhere.

  • A diagram of a deterministic acceptor is missing several arrows. Is the machine ill-defined?
    Usually not — it is drawing shorthand. The convention is that every undefined state-and-symbol pair goes to an implied non-accepting trap that loops to itself. Confirm that reading is intended, because if the author meant a real transition instead, the machine accepts a different language than the diagram suggests.
  • When can a streaming validator built on such an acceptor reject before the input ends?
    Only when the run has entered an absorbing state — one every symbol maps back to itself — so its accept status is final. A trap is the common case. Residue-style machines have no absorbing state, so they must read to the end.
  • Can a trap state ever be accepting?
    An absorbing accepting state is perfectly legal and is common in machines for 'contains this pattern', where nothing after a match can un-match it. It is not called a trap, though: the trap is specifically the absorbing non-accepting sink used to complete a machine.

saying these in an interview costs you the question

  • Says a run with no defined transition simply halts and rejects
  • Makes the trap state accepting so the machine can flag an error
  • Thinks a diagram with missing arrows is an incomplete definition
  • Adds one trap per kind of malformed input
  • Believes a total transition rule already means the machine is correct