A marble is dropped at A or B. Levers x1, x2, and x3 cause the marble to fall either to the left or to the right. whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next marble will take the opposite branch.
Model this toy as a nite automaton. An input to the atomaton is a string over the alphabet fA;Bg, which represents a sequence of marbles being dropped into the toy. The toy is initially in the con guration, above, before any marbles are dropped. Say that a sequence of marble
drops is accepted exactly in the case that if one additional marble were to be dropped in, it would go out through D regardless of where it was dropped.