A sequence detector watches a serial stream of bits, one per clock, and raises its output when the latest bits spell out a target pattern. It's the classic finite state machine design exercise, and real hardware uses the idea to find frame markers and sync words in serial data.
The states record how much of the pattern has been matched so far: for 010, "nothing", "seen 0" and "seen 01". Then:
- Progress arrows: each partial match plus the next pattern bit leads to the next partial match.
- Every other arrow: append the new bit and keep the longest ending that is still a start of the pattern. That's the suffix rule. It stops you throwing away progress you still have.
Two choices shape the design:
- Mealy or Moore. An n-bit pattern needs n Mealy states, or n + 1 Moore states (the extra one shows the match).
- Overlapping or non-overlapping. Only the arrows taken right after a match change.
Always check a finished detector by tracing an input you've counted by hand, including a near miss.