Some more on the equivalent transformation of nondeterministic finite automata. Part I. Notation and the "combining" algorithm

Abstract

This paper can be viewed as a continuation of our following previous papers, where we considered some simple algorithms for combining states of the given nondeterministic finite automaton, the reduction some problems related to the star-height to considering automata, and possible classification of the states and loops of the given automaton. In this paper, we shall describe an algorithm which combines some states of a given nondeterministic finite automaton. However, unlike algorithms published before, we have more stringent requirements for two combined states of the considered automaton. Besides, we obtain (after combining these two states) the automaton, which is not only equivalent to the given one, but also has the value of star-height which is no more  than such value for the given automaton. We also consider an example of using the described combining algorithm. In the following parts of this paper, we are going to describe the algorithms for deleting and adding a state. These algorithms will have the same features of transformations, i.e. the values of star-height for the obtained automata will be no more than such value for the given automaton.