An approach to the classification of the loops of finite automata. Part II: The classification of the states based on the 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 II of the paper, we are considering issues of a special classification of states of any nondeterministic finite automaton. This classification is based on the application of developed in the first part of this paper classification of the loops.


Full Text:

PDF

References


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.

Melnikov B. and Tsyganov A. The state minimization problem for nondeterministic finite automata: The parallel implementation of the truncated branch and bound method. Proceedings of the International Symposium on Parallel Architectures, Algorithms and Programming, PAAP-2012. Taipei, Taiwan. 2012, pp. 194-201.

Melnikov B. and Melnikova A. Pseudo-automata for generalized regular expressions. International Journal of Open Information Technologies. 2018, vol. 6, no. 1, pp. 1-8.

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.

Polak L. Minimalizations of NFA Using the Universal Automaton. International Journal of Foundations of Computer Science. 2004, vol. 16, no. 5, pp. 457-504.

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.

Dolgov V. and Melnikov B. Postroenie universal'nogo konechnogo avtomata. I ... [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, texttt{https://elibrary.ru/item.asp?id=20267924)

Dolgov V. and Melnikov B. Postroenie universal'nogo konechnogo avtomata. II ... [The construction of a universal finite automaton. Part II: Examples of work of algorithms]. Vestnik of Voronezh State University.

, no. 1, pp. 78-85. (in Russian, texttt{https://elibrary.ru/item.asp?id=21445963)

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

Kameda T. and Weiner P. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers. 1970, vol. C-19, no. 7, pp. 617-627.

Jiang T. and Ravikumar B. Minimal NFA problems are hard. SIAM Journal on Computing. 1993, vol. 22, no. 6, pp. 1117-1141. Yo-Sub Han. State elimination heuristics for short regular expressions. Fundamenta Informaticae. 2013, vol. 128, pp. 445-462.

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

Gera R., Hedetniemi S., and Larson C., editors. Graph Theory: Favorite Conjectures and Open Problems - 1. Springer, 2016, 291 p.

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.


Refbacks

  • There are currently no refbacks.


Abava   MSU conference 2018

ISSN: 2307-8162