Extended basis finite automaton. Part I. The basic definitions

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we consider a special extension of the class of non-deterministic finite automata. The purpose of this consideration is the following: first, to describe using such automata various brute-force algorithms of equivalent transformation of automata; secondly, the application of the described extension in several minimization problems for ordinary non-deterministic finite automata; thirdly, with the help of these automata we can simplify some proofs, which are also necessary for ordinary finite automata. In the paper, we consider the definition of extended finite automata, give examples, define the extended basic finite automaton for the given regular language and consider some properties of this automaton. We also prove, that for the extended basis automaton all the auxiliary languages obtained in the constructions are regular. All this allows to simplify the definition of an extended basic automaton. We also show the adequacy of the definition of an extended basis finite automaton, i.e. we prove the assertion that the extended basic automaton constructed on the basis of the source regular language really defines this language. And on one of the examples we show the following fact: there are regular languages, in whose basic automata some vertices do not have cycles corresponding to the cycles of the corresponding vertices of other equivalent automata; such cycles exist in similar vertices of extended basic automata.

Full Text:

PDF (Russian)

References


Melnikov B., 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. – P. 495–506.

Melnikov B., Melnikova A. Pseudo-automata for generalized regular expressions // International Journal of Open Information Technologies. – 2018. – Vol. 6. No. 1. – P. 1–8.

Melnikov B. Extended nondeterministic finite automata // Fundamenta Informaticae. – 2010. – Vol. 104. No. 3. – P. 255–265.

Salomaa A. Jewels of formal language theory. – Maryland, USA: Computer Science Press, Inc., 1981. – 144 p.

Melnikov B. On a classification of sequential context-free languages and grammars // Vestnik of Moscow University. Series 15: Computational Mathematics and Cybernetics. – 1993. – No. 3. – P. 64–67.

Vylitok A., Zubova M., Melnikov B. On an extension of the class of finite automata for defining context-free languages // Vestnik of Moscow University. Series 15: Computational Mathematics and Cybernetics. – 2013. – No. 1. – P. 39–45.

Generalova T., Melnikov B., Vylitok A. On the problem of vertex optimization of bracketed automata // International Journal of Open Information Technologies. – 2018. – Vol. 6. No. 9. – P. 1–8.

Han Y.-S., Wood D. The generalization of generalized automata: expression automata // Proceedings of The 9th International Conference on Implementation and Application of Automata. – 2004. – P. 114–122.

Melnikov B., Melnikova A. Multidimensional minimization of nondeterministic finite automata (Part I. Auxiliary facts and algorithms) // News of Higher Educational Institutions. Volga Region. Physical and Mathematical Sciences. – 2011. – No 4 (20). – P. 59–69.

Melnikov B., Melnikova A. Multidimensional minimization of nondeterministic finite automata (Part II. Basic algorithms) // News of Higher Educational Institutions. Volga Region. Physical and Mathematical Sciences. – 2012. – No 1 (21). – P. 31–43.

Baumgärtner S., Melnikov B. Мультиэвристический подход к проблеме звездно-высотной минимизации недетерминированных конечных автоматов // Vestnik of Voronezh State University. Series: System Analysis and Information Technologies. – 2010. – No. 1. – P. 5–7.

Melnikov B., 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. – P. 194–201.

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. – P. 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. – P. 1–6.

Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems //Fundamenta Informaticae. 2010. – Vol. 104. No. 3. – P. 267–283.

Melnikova A. Using state-marking functions when working with the loops of the basis finite automaton // Vestnik of Tambov State University. Series: System Analysis and Information Technologies. – 2015. – Vol. 20. No 5. – P. 1310–1312.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. – 2017. – Vol. 5. No. 10. – P. 9–17.

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. – P. 475 – 485.

Melnikov B., Sayfullina M. On some algorithms for the equivalent transformation of nondeterministic finite automata // News of Higher Educational Institutions. Mathematics. – 2009. – No 4. – P. 67–721.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162