Lower bound for the number of states of purposeful deterministic automata (Q796993)

The problem of the complexity of deterministic expedient automata in homogeneous Markov media is studied, considering as complexity measure of automata the number of internal states. After the detailed presentation of the problem, the following results are presented: a lower bound \(N\geq 2k\) for the number of states of Moore expedient automata in homogeneous Markov media and a lower bound \(N>k^{3/2}\) for the number of states of T-expedient automata, i.e. Moore expedient automata in homogeneous Markov media in the case when any state is chosen as initial.