Library

DFA · Regular

Lights Out on a 2 × 2 board

All four lights start on. Pressing one toggles it and its two neighbours. Accepted: the press sequences that turn everything off. The moves commute and each is its own inverse, so what matters is only which buttons were pressed an odd number of times.

1111100001000010000100110101011010011010110011101101101101110000
The machine as drawn — 16 states, 64 transitions.

The author’s examples, run

1234 → accept321411242433 → accept42221344 → accept134122142343 → accept2234 → reject121411242433 → reject12221344 → reject234122142343 → reject