Library

DFA · Regular

Rolling a die until 6 is on top

A die rolls N, S, E or W, and the machine accepts when 6 faces up. The die has 24 orientations, but only one fact matters for this question — which way the 6 is facing — so the minimal DFA has six states, not 24.

downSNWEupNSEWNSEWNSE, WNSE, WEWN, SWEN, S
The machine as drawn — 6 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

EE → acceptNSWW → acceptWSNNESSEW → acceptSWNWSESWNENNSE → acceptNE → rejectSSWW → rejectNSNNESSEW → rejectNWNWSESWNENNSE → reject