Part 3. Mathematical models

About number of states of automaton modifying its diagram

D. O. Maslenikov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Definitions of a rule and a result of applying it to а finite automaton are introduced.
The present paper considers the result of applying the rule to the automaton as a boundedly deterministic function and a finite automaton that realizes this function.
Equivalence of two definitions of a result of applying a rule to an automaton is proved. The paper provides estimations of largest and smallest number of states of the automaton.

Keywords: finite automaton, self-modifying finite state machine, Moore diagram