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

Boris Melnikov

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.


Full Text:

PDF

References


Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 267-283.

Melnikov B., and Sayfullina M. On some algorithms for the equivalent transformation of nondeterministic finite automata. Izvestiya of Higher Educational Institutions. Mathematics. 2009, no. 4, pp. 67-72. (in Russian, https://elibrary.ru/item.asp?id=11749888)

Melnikov B., and Melnikova A. Some properties of the basis finite automaton. The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2002, vol. 9, no. 1. pp. 135--150.

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. (http://injoit.org/index.php/j1/article/view/581)

Melnikov B., and 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. (http://injoit.org/index.php/j1/article/view/613)

Melnikov B., and 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. (http://injoit.org/index.php/j1/article/view/620)

Melnikov B. textit{On the star-height of a regular language. Part IV: The detailed description of the algorithm of equivalent transformation. Heuristic algorithms and distributed calculations. 2014, vol. 1, no. 5, pp. 57-75. (in Russian, https://elibrary.ru/item.asp?id=23033967)

Melnikov B. Extended nondeterministic finite automata. Fundamenta Informaticae. 2010, vol. 104, no. 3, pp. 255--265.


Refbacks

  • There are currently no refbacks.


Abava   FRUCT 2019

ISSN: 2307-8162