On the Lower Bound for the Number of States of Deterministic Intelligent Automata

The article examines the problem of estimating the complexity of deterministic Moore automata that are intelligent in homogeneous Markov media (HMM). The measure of complexity of the automaton is determined as the number of its internal states. A lower bound $N\geq 2k$ is established for the number of states of automata that are intelligent in HMM; this bound improves the earlier bound $N>k$ (here $k$ is the number of controls). A lower bound $N>k^{3/2}$ is established for the number of states of automata that are intelligent in HMM, for the case in which any of their states is taken as the initial one.