An approach to the classification of the loops of finite automata. Part I: Long corresponding loops

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we considered questions of the possible classification of the states and loops of a nondeterministic finite automaton. For the development of  algorithms for equivalent transformation of nondeterministic finite automata, we consider the basis finite automaton for the given regular language and the paths and loops of its transition graph. We also consider the paths and loops of the transition graph of another nondeterministic automaton that defines the same language. On the basis of this, we define corresponding paths and loops of two mentioned automata and the questions of their classification. This classification gives, for example, the possibilities for describing some heuristic algorithms for minimization of nondeterministic automata. For the last thing, we describe the following objects. For each state of the basis automaton, we consider the states of the given automaton corresponding to this state of the basis automaton, and give their classification as a function of the loops passing through the same state of the basis automaton. Their subset is the set of so-called including loops, on the basis of which we determine so-called partially complete loops. For any chosen vertex of the basic automaton, we call the vertices of the considered nondeterministic automaton, through which all possible partially complete loops pass, by complete cyclic states. At the end of the paper, we formulate the hypothesis that if for any state of the considered nondeterministic automaton, there exists at least one corresponding state of the basis automaton, such that the first one is a complete cyclic state for the second one, then all the corresponding states of the basis automaton are such ones. In the presented Part I of the paper, we consider the issues related to corresponding loops of the given nondeterministic automaton and equivalent basis automaton.


Full Text:

PDF

References


Melnikov B. and Vakhitova A. Some more on the finite automata. The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 1998, vol. 5, no. 3. pp. 495-506.

Melnikov B. and Melnikova A. Edge-minimization of non-deterministic finite automata. The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2001, vol. 8, no. 3. pp. 469-479.

Melnikov B. and Sayfullina M. O nekotoryh algoritmah ekvivalentnogo preobrazovaniya nedeterminirovannyh konechnyh avtomatov [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. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundamenta Informaticae. 2010, vol. 104, no. 3. pp. 267-283.

Dolgov V. and Melnikov B. Postroenie universal'nogo konechnogo avtomata ... [The construction of a universal finite automaton. Part I: From theory to practical algorithms]. Vestnik of Voronezh State University. 2013, no. 2, pp. 173-181. (in Russian, https://elibrary.ru/item.asp?id=20267924)

Dolgov V., Melnikov B. and Melnikova A. Cikly grafa perehodov bazisnogo avtomata ... [Loops of the transition graph of a basic automaton and related questions]. Vestnik of Voronezh State University. 2016, no. 4, pp. 95-111. (in Russian, https://elibrary.ru/item.asp?id=27257800)

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

Melnikov B. A new algorithm of the state-minimization for the nondeterministic finite automata. The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 1999, vol. 6, no. 2. pp. 277-290.

Geldenhuys J., van der Merwe A. and van Zijl L. Reducing Nondeterministic Finite Automata with SAT Solvers. Proceedings of 8th International Workshop on Finite State Methods and Natural Language Processing, Lecture Notes in Artificial Intelligence. July 2009, vol. 6062, pp. 81-92.

Kirsten D. Distance desert automata and the star height problem. Informatique Theorique et Applications. 2005, vol. 39, no. 3. pp. 455-509.

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.

Bender E. Mathematical Methods in Artificial Intelligence. Wiley-IEEE Computer Society Press (Los Alamitos), 1996, 656 p.

Melnikov B. O zvyozdnoy vysote regulyarnogo yazyka ... [On the star-height of a regular language. Part II: Auxiliary constructions]. Heuristic algorithms and distributed computations. 2014, no. 2, pp. 69-81. (in Russian, https://elibrary.ru/item.asp?id=22030666)

Lombardy S. and Sakarovitch J. The Universal Automaton. Logic and Automata, Texts in Logic and Games, Amsterdam Univ. Press. 2008, vol. 2, pp. 457-504.

Harary F. Graph Theory. Addison Wesley (Boston), 1969, 274 p.


Refbacks

  • There are currently no refbacks.


Abava   MSU conference 2018

ISSN: 2307-8162