Resumen
This paper discusses (non-deterministic) finite automata of a special kind. We have not found any publications in the literature in Russian that define the title for such automata, so we propose a new name for them, i.e. ?petal automata?. (In the only publication found in the Englishlanguage literature, the term ?semi-flower automata? is used, apparently it is not very successful.) The study of such automata is very important for several topics discussed in our previous publications. First of all, it is a connection with algorithms for solving problems, related to various variants of the study of the equality of infinite iterations of two finite languages: in particular, to the description of algorithms for solving these problems in the form of a special type of nondeterministic finite automata (i.e., PRI and NSPRI automata). Other problems are also close to this topic, which, in principle, can also be solved by considering all subsets of the set of potential word roots of a given language: for example, it is the problem of extracting the root of some power for the given language. But a very important auxiliary purpose is to solve these problems using algorithms, less complex than exponential ones. Two more possible topics of the applications of petal automata are as follows. It is possible to apply the obtained results in auxiliary algorithms necessary for more general algorithms of state- and edge-minimization of nondeterministic finite automata. In addition, the study of petal automata can be associated with the study of the binary relation table #, since variants of such tables divide the whole set of regular languages into special equivalence classes. The possibility of using petal automata in the last topic follows from the main result of this paper, namely, from the considered description of the algorithm for constructing such a petal automaton, the table of binary relation # of which is the same as the given table (perhaps, with the only specially added right column). In the proposed first part of this paper, the main definitions are given and the initial phase of the required algorithm for constructing a petal automaton is considered (using the example only). This phase is associated with special transformations of the complete automaton for a given table of the binary relation #; these transformations, generally speaking, are nonequivalent, but at the same time preserving this binary relation.