Day 29: Design a sequence detector FSM cold (the “101” detector)
The canonical FSM interview problem
Detect the pattern 101 in a serial bit stream, asserting an output the cycle the pattern completes. Two variants: non-overlapping (restart fully after a match) and overlapping (the trailing 1 of one match can start the next — so 10101 yields two detections). Build it as a Mealy machine, whose output can assert on the transition that completes the pattern.
State meaning:
S0 = no useful prefix S1 = seen "1" S2 = seen "10"
Cur | in | Next | y (output)
----+----+------+-----------
S0 | 0 | S0 | 0
S0 | 1 | S1 | 0
S1 | 0 | S2 | 0
S1 | 1 | S1 | 0
S2 | 0 | S0 | 0
S2 | 1 | S1 | 1 <- completes 1-0-1, and "1" starts a new prefix
Test stream 1 1 0 1 0 1 -> detect at the 4th and 6th bits (overlapping).Implement and simulate the 101 detector
Draw the diagram and table from scratch (no notes), then implement the FSM and run it against a test bit stream — by hand now, and again on the Python simulator you build on Days 30–31. Confirm the overlapping behavior on 10101. Being able to produce this cold is a genuine interview asset.
One pattern, a whole family
Once you can do 101, you can do 110, 1011, or any pattern: the states simply track 'how much of the target prefix have I matched so far,' and overlapping just means a completed match falls back to the longest still-valid prefix rather than to the start. Interviewers vary the pattern to see if you understood the *method*, not memorized one answer.
Ship for Day 29
In the overlapping "101" detector, after a match completes on input 1, why does the FSM go to the "seen 1" state rather than back to the start?
