Automata – complete invariants for strongly connected regular languages

Boris Melnikov

Abstract


In this paper, we continue to consider strongly coupled automata, as a subset of ordinary nondeterministic finite automata. Based on this, strongly related regular languages are naturally defined. We consider some properties of the concept of the strong connectedness, in particular, the non­closure of this class with respect to ordinary set­theoretic operations. The title of the paper includes the word “invariants”; such ones for the regular languages are not only the canonical automata (besides, they are complete invariants), but also the canonical automaton for the mirror language, as well as the basis and universal automata, which ones (for strongly connected languages) are the main subject of this paper. One of the important incomplete invariants is the binary relation #, which is also discussed in this paper. We show the connection of the concept of “strong connectedness” with the basic and universal finite automata. Thus, for a strongly connected language, the basic automaton is not necessarily strongly connected, and the universal automaton is necessarily so. We consider the last fact to be the most important result related to strongly connected languages: it allows us to equivalently reformulate the definition of a strongly connected regular language, such can be considered a language for which its universal automaton is strongly connected. We illustrate the consideration of basis and universal automata for strongly connected languages with some examples, the consideration of which was started in the previous paper on strongly connected languages.

Full Text:

PDF (Russian)

References


Melnikov B. On a subclass of the regular language class (“strongly connected” languages): definitions and corresponding canonical automata // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 3. – P. 1–10 (in Russian).

Thierrin G. Permutation automata // Mathematical Systems Theory. – 1968. – No. 2. – P. 83–90.

Krawetz B., Lawrence J., Shallit J. State complexity and the monoid of transformations of a finite set // International Journal of Foundations of Computer Science. – 2005. – Vol. 16. No. 3. – P. 547–563.

Singh S. N. Semi­Flower Automata. PhD thesis // Indian Institute of Technology Guwahati, 2012.

Singh S. N., Krishna K. V. The rank and Hanna Neumann property of some submonoids of a free monoid // Annals Math. Inform. – 2012. – Vol. 40. – P. 113–123 (arXiv:1112.4250).

Singh S. N., Krishna K. V. A sufficient condition for the Hanna Neumann property of submonoids of a free monoid // Semigroup Forums. – 2013. – Vol. 86. No. 3. – P. 537–554.

Melnikov B. F. Regular languages and nondeterministic finite automata: monograph. – Мoscow: Russian State Social University Ed., 2018. – 179 p. (in Russian).

Melnikov B., 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. – P. 135–150.

Melnikova A. Some properties of the basis automaton // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2012. – No. 2. – P. 184–189 (in Russian).

Dolgov V., Melnikov B. Construction of a universal finite automaton. I. From the theory to the practical algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2013. – No. 2. – P. 173–181 (in Russian).

Dolgov V., Melnikov B. Construction of a universal finite automaton. II. Examples of how algorithms work // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2014. – No. 1. – P. 78–85 (in Russian).

Melnikov B., Dolgov V. Some more algorithms for Conway’s universal automaton // Acta Universitatis Sapientiae, Informatica. – 2014. – Vol. 6. No. 1. – P. 5–20.

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

Jiang T., Ravikumar B. Minimal NFA problems are hard // SIAM Journal on Computing (SICOMP). – 1993. – Vol. 22. No. 6. – P. 1117– 141.

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


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162