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

Boris Melnikov

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.

Full Text:

PDF

References


Melnikov B. Some more on the equivalent transformation of nondeterministic nite automata. Part I. Notation and the “combining” algorithm // International Journal of Open Information Technologies. 2019, vol. 7, no. 4, pp. 1–5.

Melnikov B. Some more on the equivalent transformation of nondeterministic nite automata. Part II. The “deleting” algorithm // International Journal of Open Information Technologies. 2019, vol. 7, no. 9, pp. 1–6.

Melnikov B. The star-height of a finite automaton and some related questions // International Journal of Open Information Technologies. 2018, vol. 6, no. 7, pp. 1–5.

Melnikov B., Melnikova A. An approach to the classification of the loops of finite automata. Part I: Long corresponding loops // International Journal of Open Information Technologies. 2018, vol. 6, no. 9, pp. 9–14.

Melnikov B., Melnikova A. An approach to the classification of the loops of finite automata. Part II: The classification of the states based on the loops // International Journal of Open Information Technologies. 2018, vol. 6, no. 11, pp. 1–6.

Melnikov B., Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2002, vol. 9, no. 2, pp. 475–485.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. 2017, vol. 5, no. 10, pp. 9–17.

Melnikov B. Regular languages and nondeterministic finite automata. – Russian State Social University Ed., 2018, 180 p. (in Russian)

Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. Amsterdam University Press, 2008, pp. 457–504.

Dedekind R. U¨ ber Zerlegungen von Zahlen durch ihre gro¨ßten gemeinsamen Teiler // Gesammelte Werke 2. Braunschweig, 1897, pp. 103–148. (in German)

Korshunov A. On the number of monotonous Boolean function // The Problems of Cybernetics. 1981, vol. 38, pp. 5–108. (in Russian)


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Fruct 2020

ISSN: 2307-8162