Library

DFA · Regular

MFM encoding: between two 1s, one to three 0s

Floppy disks recorded data in MFM, whose bit stream obeys a (1,3) run-length limit: two 1s are separated by at least one 0, so pulses never crowd, and at most three, so the clock never drifts. The DFA counts the 0s since the last 1.

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

The author’s examples, run

ε → accept0010 → accept0 → accept0000000010 → accept0110 → reject1000000010 → reject11 → reject00110 → reject