In a nondeterministic finite automaton, a symbol can lead to several states or none — what does it mean to accept a string?
answer
- choice, not one forced next step
- many runs, not a single trace
- existence, not agreement
- a dead branch is not a rejection
- reject only when every run fails
basics
~20 sAcceptance is existential: the machine accepts a string when at least one run over it ends in an accepting state. Runs that die on a missing transition, or finish in a non-accepting state, simply contribute nothing.
solid answer
~40 sA nondeterministic finite automaton has a transition *relation* rather than a function, so one state and one symbol may yield several successors, one, or none. Reading a string therefore produces a whole family of runs instead of a single trace. The machine **accepts** the string when *at least one* of those runs ends in an accepting state; the input is rejected only when every run either dies on a missing transition or finishes somewhere non-accepting. That is an existential rule, not a majority vote and not luck — nondeterminism here is not randomness. You can evaluate it without guessing by carrying the whole set of currently reachable states forward one symbol at a time, which is exactly the idea the subset construction freezes into a table.
go deeper
Recall the shape of the definition: several successors allowed, or none, and the string is accepted if some path through the machine reaches an accepting state.
Explain acceptance as an existential rule over runs, say precisely what happens to a branch that dies, and show the live-set simulation that evaluates it in one forward pass.
Show why the model is worth using in a shipped scanner: a guess-where-it-starts machine is trivial to generate and obviously correct, and determinisation is a separate implementation decision.
Frame nondeterminism as a specification convenience with a known implementation cost, and be ready to say where that cost is paid — build time, table memory or per-symbol work.
## Choice instead of a single next step A **deterministic finite automaton (DFA)** has a *total transition function*: in state `q`, on symbol `a`, there is exactly one successor. A **nondeterministic finite automaton (NFA)** relaxes this to a *transition relation*: in state `q` on symbol `a` there may be several successors, exactly one, or none at all. Many presentations also allow an **epsilon move**, a transition taken without consuming any symbol. Everything else is identical — a finite alphabet, a finite state set, one start state, a designated set of accepting states. The name invites the wrong mental picture: a machine that flips a coin at each fork and might get unlucky. That is not the definition. Nondeterminism is not randomness, not a scheduler and not a probability distribution. It is a statement about the *set* of runs the machine has on a given input, and the acceptance rule quantifies over that set. ## Acceptance is existential A **run** on an input string `w` is a sequence of states starting at the start state, where each step follows some transition allowed for the next symbol of `w` (epsilon moves may be interleaved and consume nothing). The machine **accepts** `w` when **at least one** run on `w` consumes all of `w` and ends in an accepting state. Four consequences follow directly, and they are where candidates usually slip: - A run that reaches a state with **no** transition on the next symbol **dies**. A dead run is not a rejection — it just stops contributing. - A run that consumes all of `w` but ends in a non-accepting state also contributes nothing. - `w` is **rejected** only when *every* run dies or ends non-accepting. - Because acceptance is existential, **adding** a transition can only add runs, so it can only make the machine accept the same strings or more. Removing one can only shrink the accepted set. | | Deterministic acceptor | Nondeterministic acceptor | |---|---|---| | Transition | function: exactly one successor | relation: zero, one or many successors | | Runs per input | exactly one | possibly many, possibly zero | | Acceptance rule | the single run ends accepting | *some* run ends accepting | | Missing transition | modelled by an explicit trap state | that branch dies | | Languages recognised | the regular languages | the regular languages — the same class | The last row is the point of the whole model: guessing buys no extra recognising power. What it buys is **concision** — often dramatically fewer states, and a machine that is far easier to write down by hand. ## Evaluating the guess without guessing You never have to enumerate runs one at a time. Carry a **set of live states**: 1. Start from the set containing the start state (closed under epsilon moves, if the machine has them). 2. On each input symbol, replace the set by the union of all successors of its members on that symbol (then close under epsilon moves again). 3. After the last symbol, accept if the live set contains any accepting state. The live set is a subset of a finite state set, so the memory is bounded no matter how long the input is, and the work per symbol depends on the machine, not on how much input has already been read. Freezing that live set into a named state of a new machine is exactly the subset construction. ## Why a working engineer meets this Picture a sensor on a network tap that must fire when a byte signature appears anywhere in a stream. The natural machine simply *guesses* at every position that the signature starts here, and idles otherwise: a self-loop on the start state for every byte, plus one chain per signature. That machine is trivial to generate and obviously correct, because a guess that is wrong just dies and a guess that is right accepts. Writing the equivalent deterministic acceptor by hand is a much larger job. Nondeterminism is the modelling convenience; determinisation is the implementation step you take afterwards when you want one table lookup per byte. ## What it is not - **Not backtracking.** Backtracking is one *implementation strategy* for searching the runs; it is not the semantics. Simulating the live set explores all runs in lock-step with no backtracking at all. - **Not parallel hardware.** The set of runs is a mathematical object, not a thread pool. - **Not extra power.** Every language accepted by a nondeterministic finite automaton is accepted by some deterministic one — possibly with far more states.
- If, after the last symbol, some runs are still in non-accepting states and none accepted, is the string accepted?No. Acceptance needs a run that has consumed the whole string *and* ended in an accepting state. Runs that survived to the end but finished non-accepting count for nothing, exactly like runs that died halfway. Having live branches left over is not partial credit.
- How do you evaluate a nondeterministic acceptor over a stream you cannot rewind?Carry the set of live states and update it once per symbol: take the union of successors of every member, then close under epsilon moves. Memory is one subset of a fixed state set, and no symbol is ever revisited, so a single forward pass suffices.
- Does adding more transitions to a nondeterministic acceptor risk losing strings it used to accept?No. Acceptance is existential, so every run that existed before still exists; new transitions only create additional runs. The accepted language can therefore only stay the same or grow. Shrinking it requires removing transitions or removing accepting states.
A hiring panel that says yes if any one interviewer says yes: the other objections do not matter, and a panellist with nothing to say simply drops out of the decision.
saying these in an interview costs you the question
- Says the machine picks one branch at random, so acceptance is luck
- Thinks a branch with no outgoing transition rejects the whole input
- Claims nondeterministic finite automata recognise strictly more languages
- Requires every run to end accepting, which is a different acceptance rule
- Treats a missing transition as an implicit self-loop on the same state
- Equates nondeterminism with backtracking search rather than with the set of runs