Some more on the equivalent transformation of nondeterministic finite automata. Part III. The “adding” algorithm

Abstract

This paper is a continuation of two previous parts. In them, we considered some simple algorithms for combining and removing (deleting) states of the given nondeterministic finite automaton, as well as the reduction some problems related to the star-height to considering automata. To do this, we used the possible classification of the states and loops of the given automaton.
In this part of the paper, we shall describe an algorithm which adds some states and edges to the given nondeterministic finite automaton. This algorithm preserves the basic properties of automata: the languages of the given and the obtained automata are the same, and the value of star-height for the obtained automaton is no more than such value for the given automaton. This algorithm is more complicated than the ones considered in the previous parts due to the following conditions. Here, we consider the case, when there exists the only direction for the paths between two considered states (we denoted them q and qm in previous parts). I.e., the path in the direction of all edges, or, vice versa, in the reverse direction; but not in both directions at the same time. (Like previous parts, we consider only such paths that do not pass through edges with smaller numbers, which are less than the value of qm; more strictly, all the considered vertices of such path should have the values of !-function defined for the “minimum” automaton less than q has.) The simple algorithms for combining these two states q and qm (similar to the algorithm discussed in Part I) increase the SH-value of the automaton under consideration. To prevent this increase, we use the removing (deletion) instead of combining, but, unlike Part II, we have to add some new elements (i.e. vertices and edges) to the transition graph of the automaton we transform.