Library

DFA · Regular

A robot that comes home

A robot in a 3 × 3 room starts in a corner and moves N, S, E or W; walking into a wall is not allowed. Accepted: the walks that end where they began. Every closed walk on this grid has even length, and the machine shows why — the squares are coloured like a chessboard.

0,00,11,00,21,12,01,22,12,2SENSESEWNENSEWSWNEWNSWNW
The machine as drawn — 9 states, 24 transitions.Every word up to length 4, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptESNW → acceptSSEENNWW → acceptESESWENNWW → acceptN → rejectNSNW → rejectNSEENNWW → rejectNSESWENNWW → reject