A sensor accepts streams whose k-th symbol from the end is a marker — why does determinising that acceptor cost 2^k states?
answer
- guessing where the end is
- idle state plus a chain of k
- no lookahead, so remember the window
- every marker pattern of k positions occurs
- states bought, power unchanged
basics
~20 sNondeterministically the machine guesses which symbol is the k-th from the end and needs only k+1 states. Deterministically nothing can guess, so it must remember which of the last k symbols were markers — and all 2^k combinations occur.
solid answer
~40 sThe nondeterministic acceptor is tiny: one state that idles on every symbol, plus a chain of `k` more. On a marker it *guesses* "this is the k-th from the end" and walks the chain; if the stream ends exactly there, some run accepted. That is `k + 1` states. A deterministic machine cannot guess and cannot look ahead, so at every position it must be able to answer for **any** ending. The only way is to carry a window of the last `k` symbols — which of them were markers — and all `2^k` windows genuinely occur, so the subset construction reaches `2^k` distinct reachable subsets (half the `2^(k+1)` bound, since the idling state sits in every one of them). Nondeterminism bought **states**, not recognising power: both machines accept exactly the same language.
go deeper
Recall the headline: a machine that may guess can be far smaller than one that may not, even though both accept exactly the same strings.
Build both machines and count: k + 1 states with guessing, 2^k reachable subsets without, and say what a subset actually records about the recent input.
Read it as a capacity fact — the table grows exponentially in the anchor distance, so know your k before choosing to determinise, and know when the machine cannot be built at all.
Treat anchoring as a design lever: a condition measured backwards from an unknown end costs an exponent that the same condition anchored at a visible delimiter does not.
## The two machines Fix an alphabet with a distinguished **marker** symbol, and the language *"the k-th symbol from the end is a marker"*. On a stream sensor this is a realistic shape: you care about a position measured backwards from wherever the stream happens to stop. **The nondeterministic acceptor** has `k + 1` states: - `s`, the start state, with a self-loop on **every** symbol — it idles, refusing to commit; - `s --marker--> c1`, the guess: *this marker is the k-th symbol from the end*; - a chain `c1 -> c2 -> ... -> ck` where every transition fires on **any** symbol; - `ck` is accepting. A run accepts when the guess was right — when exactly `k - 1` symbols followed that marker and then the stream ended. Wrong guesses walk off the end of the chain or finish early and die, which costs nothing. The machine is trivial to write down and obviously correct, and that is the entire value of nondeterminism as a modelling tool. ## Why determinising explodes Run the subset construction. After reading a stream `w`, the live subset is `{s}` together with `{cj : the j-th symbol from the end of w is a marker, for j <= k}`, because entering `c1` requires a marker and each further chain step consumes exactly one symbol. That subset **is** the window of the last `k` symbols, recorded as "marker or not" per position. And every one of those windows is reachable: choose the last `k` symbols of the stream freely. So: - reachable subsets: `2^k`, one per pattern of the last `k` positions; - the general bound for `n = k + 1` original states: `2^(k+1)`; - the gap: exactly a factor of two, because `s` idles on every symbol and therefore belongs to **every** reachable subset — no subset omits it, and the empty subset never occurs. The cause is not the construction being wasteful. It is that a deterministic machine has **no lookahead**: at each position it must already hold whatever a future ending could ask about, and here that is the whole `k`-symbol window. | | Nondeterministic | Determinised | |---|---|---| | States | `k + 1` | `2^k` | | What a state holds | "how far along a guess am I" | the marker pattern of the last `k` symbols | | Per-symbol work | update a live set of size at most `k + 1` | one table lookup | | Table memory | negligible | `2^k` times the alphabet size | | Language accepted | identical | identical | Put numbers on it: `k = 8` gives 256 subsets — nothing. `k = 20` gives roughly a million. `k = 40` is past a trillion, so the table cannot be built at all, while the nondeterministic machine still has 41 states. The blow-up is real, it is not an artefact, and it is why this language is the standard witness for it. ## What this does and does not prove - It **does** show that determinisation can cost exponentially many states for a natural language, and that the cost shows up as table memory and build time rather than as anything at match time. - It **does not** show that nondeterminism recognises more: both machines accept exactly the same strings, and the subset construction works here as it does everywhere. Guessing bought **concision**. - It **does not** by itself establish that `2^k` cannot be beaten by a cleverer deterministic machine. That is a lower-bound argument about minimal machines, which is a separate piece of theory; what the construction alone tells you is that this many distinct reachable subsets exist. - It **does not** mean determinisation is generally exponential. Most machines you would actually generate determinise to something modest; `2^n` is a worst-case bound that this language is built to hit. ## The engineering reading If your sensor's condition is anchored at the **end** of a stream whose length you do not know in advance, you are asking for a fixed-width memory of the recent past, and the deterministic state count follows directly from that width. Anchoring the same condition at the **start** of the stream, or at a delimiter you can see, removes the guess and with it the exponent. Choosing where a condition is anchored is therefore a design decision with an exponential consequence, not a cosmetic one.
- How many states does the nondeterministic acceptor for this language need, and why that many?`k + 1`: one idling state with a self-loop on every symbol, plus a chain of `k` states entered on a marker and advanced by any symbol, with the last one accepting. The idling state is what lets the machine defer the guess to any position in the stream.
- Why does the reachable subset count come out at 2^k rather than the 2^(k+1) bound?The idling start state has a self-loop on every symbol, so it appears in every reachable subset and the empty subset never occurs. The only freedom left is which of the `k` chain states are present, giving `2^k` subsets — exactly half the bound.
- Does this example mean determinisation is usually exponential in practice?No. It is a worst-case witness, constructed so that every subset is reachable. The subset construction builds only reachable subsets, and for most machines that is a modest number. The lesson is to bound the count for the machines you actually generate, not to assume the exponent.
- What changes if the same condition is anchored at the start of the stream instead of the end?The exponent disappears. "The k-th symbol from the start is a marker" needs no guess: a deterministic machine counts to `k`, checks that symbol, then idles — about `k + 2` states. The blow-up comes entirely from the position being measured against an end the machine cannot see coming.
Being asked at every street corner what the light showed k blocks ago: with no way to know which corner will be the last one, you have to carry the whole record of the last k blocks with you.
saying these in an interview costs you the question
- Concludes the nondeterministic machine recognises a language no deterministic one can
- Says the determinised machine needs a counter for the remaining stream length
- Claims determinisation always produces 2^n states for n input states
- Thinks the blow-up is a flaw in the subset construction rather than in the language
- Believes the exponential cost is paid per input symbol at match time
- Assumes the machine can look ahead to find where the stream ends