Library

DFA · Regular

Every window of five has two 0s

Every block of five consecutive symbols contains at least two 0s. A sliding-window property: the machine need only remember the last four symbols, and in fact fewer distinctions than that — minimised, it has fifteen states rather than the sixteen windows, because two windows behave alike.

start0101101101110111011101111011110111101111
The machine as drawn — 15 states, 24 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → accept00110 → accept0 → accept0000000110 → accept01111 → reject111100 → reject0001111 → reject00001111 → reject