A discrete system that models the operation of a dynamic finite state machine (automaton) with memory is considered. In distinction from the classical model of discrete time system, in which the states are changed (switched) at prescribed instants of time, automaton-type systems may change their states at arbitrary instants. Moreover, multiple instantaneous switchings are allowed. Furthermore, the choice of the instants when the automaton “fires” and the number of switchings at these instants are considered as control resources, and they are subject to optimization. Sufficient optimality conditions for such systems are proved. Equations for the optimal open-loop control and for the value (Bellman) function are derived. A method for the synthesis of the optimal control is proposed based on the construction of the value function as the lower envelope of a family of auxiliary functions (generators). Application of the proposed method is illustrated by examples.