Overlapping detection

Also called: overlapping, overlapping sequence detection, overlapping detector

A sequence detector mode in which the bits of one match may also count toward the next match, so 1111 contains three matches of 11.

When a sequence detector finds its pattern, what happens to those bits? In overlapping detection they stay available: the end of one match can be the start of the next.

Count 11 in 1, 1, 1, 1 by sliding a two-bit window one place at a time: positions 1–2, 2–3 and 3–4 all match. Three matches.

In the machine, this only affects the arrow taken at a match. Instead of going back to "nothing", it goes to the state for the longest ending of the matched string that is still a start of the pattern. That's just the suffix rule applied to the completing arrow.

Mealy 010: the match arrow goes to "seen 0", since the final 0 can start the next 010.
Mealy 110: the match arrow goes to "nothing", because no ending of 110 starts 110. For this pattern, overlapping and non-overlapping machines happen to be identical.

Overlapping is the usual default in hardware, because a real bit stream doesn't reset itself after a match.

Worked examples

Example

Overlapping 010

The diagram is the overlapping Mealy 010 detector (A = nothing, B = seen 0, C = seen 01). Apply 0, 1, 0, 1, 0.

1.
0: A → B, 0. 1: B → C, 0.
2.
0: C → B, 1. The match keeps its final 0 as "seen 0".
3.
1: B → C, 0. 0: C → B, 1.
4.
Outputs 0, 0, 1, 0, 1: two matches, sharing input 3.

Example

Counting by hand

How many overlapping matches of 101 are in 1, 0, 1, 0, 1, 0, 1?

1.
Slide a 3-bit window: 101, 010, 101, 010, 101.
2.
Matches end at inputs 3, 5 and 7.
3.
Three matches.

Common mistakes

Resetting to "nothing" after every match, which turns an overlapping detector into a non-overlapping one.
Changing arrows other than the match arrow. Overlap only matters at the moment a match completes.

Practice Overlapping detection

Interactive questions with instant feedback and a worked solution for every wrong answer.

Finite State Machines lesson full course

And 7 more in the Finite State Machines lesson.

Practice exams

Learn it step by step

Overlapping detection is taught in Finite State Machines.

Finite State Machines →

All terms