skip to content

In a deterministic finite acceptor for strings containing 1 1 0, why can't a mismatch reset the run to the start state?

level: seniorimportance: should knowfreq 40%

answer

  1. the near miss is not wasted
  2. states describe the suffix, not an attempt
  3. how much of the pattern ends here
  4. a failing symbol may start the pattern
  5. matched state absorbs everything after

basics

~20 s

Because the symbol that broke the match can itself begin the next one. Each state records the longest prefix of 1 1 0 that ends the input so far, so after 1 1 1 the machine must stay at two matched symbols rather than drop to zero.

solid answer

~40 s

The states of a "contains this pattern" acceptor are not attempts, they are **how much of the pattern currently ends the input**: state `k` means the last `k` symbols read are the first `k` symbols of the pattern, and nothing longer qualifies. A mismatch therefore does not throw away everything — it asks what is still true of the suffix. Reading `1 1 1` against the pattern `1 1 0`, the third `1` breaks the match, but the last two symbols are still `1 1`, so the machine stays in state 2. A machine that reset to the start here would reject `1 1 1 0`, which plainly contains `1 1 0`. Once the whole pattern has matched, the accepting state absorbs everything, because nothing later can un-contain it.

code

pseudocode · 15 lines
pseudocode
# language: digit strings containing 1 1 0
# state k = length of the longest suffix read so far that is a prefix of 1 1 0

delta[0][1] = 1 ; delta[0][0] = 0
delta[1][1] = 2 ; delta[1][0] = 0
delta[2][1] = 2 ; delta[2][0] = 3   # overlap: 1 1 1 still ends in 1 1
delta[3][1] = 3 ; delta[3][0] = 3   # accepting and absorbing

state = 0
for each symbol s in input:
    state = delta[state][s]

accept if state == 3

# trace of 1 1 1 0 : 0 -> 1 -> 2 -> 2 -> 3, accepted

go deeper

for a junior

Know that the machine tracks how much of the pattern is currently matched, and that a symbol which breaks the match can still be the start of a new one.

for a middle

State the invariant precisely as the longest suffix of the input that is a prefix of the pattern, and derive each table entry from it instead of guessing arrows.

for a senior

Recognise the reset bug as a false negative that ordinary test data hides, and be able to name an input that exposes it and explain why routine cases pass.

for a principal

Frame it as a correctness-by-construction argument: a stated state invariant lets a reviewer check a validator's table entry by entry, which hand-written matching logic does not give you.

## What the states mean For the language "strings containing `1 1 0` somewhere", build the machine with **four states**, numbered 0 to 3, and give each a precise meaning: - **State `k`** = the longest suffix of the input read so far that is also a prefix of `1 1 0` has length `k`. - **State 0** — no useful suffix; the input so far ends in nothing the pattern could start with. - **State 3** — the pattern has occurred. It is **accepting and absorbing**: every symbol loops back, because containment cannot be undone. Stating the invariant this way is the whole design. It is a property of the *string read so far*, not of an attempt in progress, which is why nothing needs to be restarted or remembered about where an attempt began. ## The overlap step The interesting entries are the ones where a symbol fails to extend the match: | state | meaning | on `1` | on `0` | |---|---|---|---| | 0 | nothing matched | 1 | 0 | | 1 | ends in `1` | 2 | 0 | | 2 | ends in `1 1` | **2** | 3 | | 3 | pattern seen | 3 | 3 | The bold entry is the one candidates get wrong. In state 2 the input ends `1 1`; reading another `1` means it now ends `1 1 1`. The longest suffix of that which is a prefix of `1 1 0` is `1 1` — length two — so the machine **stays in state 2**. Dropping to state 1 or 0 would forget a genuine partial match. The same reasoning explains state 2 on `0` going to 3 and state 1 on `0` going to 0: after `1 0` the input ends in `0`, and `0` is not a prefix of `1 1 0`, so nothing is left over. ## The bug a reset causes Trace `1 1 1 0` two ways: 1. **Correct machine:** 0 → 1 → 2 → 2 → 3. Accepted, and rightly so: the last three symbols are `1 1 0`. 2. **Reset-on-mismatch machine:** 0 → 1 → 2, then the third `1` "fails" and the run restarts at 0, then `0` keeps it at 0. Rejected. That is a false negative in a validator, and it is the kind that survives testing: every input with a clean, isolated occurrence of the pattern passes, so the defect shows only when the pattern's own symbols overlap. `1 0 1 0` is correctly rejected by both machines, because it really does not contain `1 1 0`; `1 1 0 1` is correctly accepted by both. Only inputs whose near-miss shares a suffix with the pattern's prefix — `1 1 1 0` here — expose the bug. ## Sizing and shape - A pattern of length `k` needs at most **`k + 1` states** for the containment language, one per possible matched length. - The accepting state is absorbing **for containment**. If the rule were "ends with the pattern" instead, the final state would not absorb, because a later symbol can spoil the ending. - Every state needs an entry for every symbol of the alphabet. With a wider alphabet, any symbol that neither extends nor overlaps the match sends the run back to state 0 — or to state 1 if it happens to be the pattern's first symbol. - Because the state is just a small number, the run has no memory of where an occurrence started. That is fine for a yes/no decision; if the position is needed, it must be tracked outside the acceptor. ## How to build the table without guessing For each state `k` and symbol `s`, write out the string `P[0..k-1]` followed by `s`, then find the **longest suffix of that string which is a prefix of the pattern**; its length is the next state. Doing this mechanically for four states and two symbols takes a minute and removes the reset error entirely. ## Where candidates go wrong - Treating a mismatch as "start over", which is the reset bug above. - Thinking the state counts symbols matched since some anchor, rather than describing the suffix of the whole input. - Making the accepting state non-absorbing for a containment rule, so a long input can lose an occurrence it already had. - Assuming the machine can report where the pattern was found; the state set has no room for a position.

  • How would the machine change if the rule were 'ends with 1 1 0' instead of 'contains 1 1 0'?
    The states and transitions stay the same, but the final state stops absorbing: from it, further symbols must be routed by the same longest-suffix rule, so a following symbol can drop the run back out of acceptance. Containment is permanent; ending with a pattern is not.
  • How many states does a containment acceptor need for a pattern of length k?
    At most k + 1, one for each matched length from zero up to the whole pattern. The count depends on the pattern's length and not on the alphabet size; a wider alphabet grows the table's width, since every state still needs an entry per symbol.
  • Can this acceptor tell you where in the input the pattern occurred?
    No. Its whole memory is one small state number describing the current suffix, with no room for a position and no counter. A yes/no verdict is all it gives; reporting the offset requires a counter kept alongside the machine by the code that drives it.

saying these in an interview costs you the question

  • Restarts the match at state zero whenever a symbol fails to extend it
  • Says the state counts symbols matched since the last attempt began
  • Believes an occurrence can be lost once the pattern has been seen
  • Thinks the acceptor also knows where the match happened
  • Claims overlap only matters when patterns repeat a whole block