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.
The author’s examples, run
ε → acceptESNW → acceptSSEENNWW → acceptESESWENNWW → acceptN → rejectNSNW → rejectNSEENNWW → rejectNSESWENNWW → reject