Simplified regular languages and a special equivalence relation on the class of regular languages. Part I

Boris Melnikov; Vasily Dolgov

Simplified regular languages and a special equivalence relation on the class of regular languages. Part I

Boris Melnikov, Vasily Dolgov

Abstract

The equivalence relation S on the class of regular languages, considered in this paper, is necessary for a more complete study of the relation R previously defined in our articles. In addition, the motivation for considering the relation S is the need to apply it to the study of so-called petal (semiflower) automata, which was also started in one of our previous papers. Specifically, in order to obtain a petal automaton, there is necessary to consider such an algorithm of the nonequivalent transformation of the automaton as the union of two letters of the considered alphabet, and both the mentioned equivalence relations on the class of regular languages, i.e. relations R and S, are associated with this transformation. In turn, petal automata arise when describing several different algorithms for checking the binary relation “equivalence at infinity”, also discussed in some our previous papers, in particular, when using PRI and NSPRI finite automata in these algorithms. Thus, in this paper we define S, a special binary relation on a set of regular languages, show the fulfillment of all the properties of equivalence relations; therefore the relation S divides the whole class of regular languages into some disjoint subclasses. As a result, for most of the problems of the theory of formal languages, we can take only one representative of each such class; and it is usually desirable to consider the so-called simplified language, it is the only in each such subclass. The concept of a simplified language is based on the combination of so-called parallel letters, and the simplified finite automaton specially introduced by us corresponds to such a simplified language. All this makes it possible to limit the number of regular languages under consideration to work with a finite number of corresponding finite automata; moreover, such automata have a pre-fixed number of states. Both these equivalence relations, S and R, preserve the relation # defined for a particular regular language, and, therefore, allow to use many previously proven properties of regular languages and nondeterministic finite automata for arbitrary automaton of its equivalence class and the corresponding language. In the presented part I, we give a definition of the relation S, then prove its simplest properties and consider a simple example.

Full Text:

PDF (Russian)

References

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

Melnikov B. Petal (semi-flower) finite automata: basic definitions, examples and their relation to complete automata. Part I // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. ??. – P. 1-11 (in Russian).

Melnikov B., Dolgov V., Melnikova E. An equivalence relation on the class of regular languages // Communications in Computer and Information Science. – 2020. – Vol. 1140. – P. 93–107.

Melnikov B. Variants of finite automata corresponding to infinite iterative morphism trees. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 7. – P. 5–13 (in Russian).

Melnikov B. Variants of finite automata corresponding to infinite iterative morphism trees. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 10. – P. 1–8 (in Russian).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 4. – P. 1–9 (in Russian).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inverse morphism // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 5. – P. 1–8 (in Russian).

Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 4. – P. 1–9 (in Russian).

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 7. – P. 1-9 (in Russian).

Melnikov B. Description of special submonoids of the global supermonoid of a free monoid // News of higher educational institutions. Mathematics. – 2004. – No. 3. – P. 46–56 (in Russian).

Melnikov B., 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. – P. 469–479.

Melnikov B., Tsyganov A. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // In: Proceedings – 5th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP–2012. – 2012. – P. 194–201.

Dolgov V., Melnikov B. On the automatic construction algorithms of Waterloo-like finite automata based on complete automata // Heuristic algorithms and distributed computing. – 2014. – Vol. 1. No. 4. – P. 24– 45 (in Russian).

Dolgov V., Melnikov B. B. Building 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).

Dolgov V., Melnikov B., Melnikova A. Cycles of the transition graph of a basic finite automaton and related issues // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2016. – No. 4. – P. 95–111 (in Russian).

Kameda T., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. – 1970. – Vol. C19. No. 7. – P. 617–627.

Polák L. Minimizations of NFA using the universal automaton // International Journal of Foundation of Computer Sciences. – 2005. – Vol. 16. No. 5. – P. 999–1010.

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

Lombardy S., Sakarovitch J. The Universal Automaton // Logic and Automata, Texts in Logic and Games, Amsterdam Univ. Press. – 2008. – Vol. 2, P. 457–504.

Melnikov B., Melnikova A. Some properties of the basis finite

automaton // The Korean Journal of Computational and Applied Mathematics (Journal of Computational and Applied Mathematics). – 2002. – Vol. 9. No. 1. – P. 135–150.

Melnikov B., Melnikova A. A new algorithm of constructing the basis finite automaton // Informatica (Lithuanian Academy of Sciences Ed.). – 2002. – Vol. 13. No. 3. – P. 299–310.

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–505.

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 star-height of a finite automaton and some related questions // International Journal of Open Information Technologies. – 2018. – Vol. 6. No. 7. – P. 1–5.

Melnikov B. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian State Social University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355-7. (in Russian).

Brauer W. Automatentheorie. Eine Einführung in die Theorie endlicher Automaten. – Stuttgart, B. G. Teubner. – 1984. – 493 S (in German).

Melnikov B., Sayfullina M. On some algorithms for equivalent transformation of nondeterministic finite automata // News of higher educational institutions. Mathematics. – 2009. – No. 4. – P. 67–72 (in Russian).

Ginsburg S. The mathematical theory of context-free languages. – Columbus, McGraw-Hill. – 1966. – 232 p.

Aho A., Ullman J. The Theory of Parsing, Translation and Compiling. Vol. 1. Parsing. NJ, Prentice Hall. – 1972. – 2051 p.

Salomaa A. Jewels of Formal Language Theory. – Rockville, Maryland, Computer Science Press. – 1981. – 144 p.

Pin J.-E. Mathematical Foundations of Automata Theory. – Berlin, Springer-Verlag. – 2012. – 310 p.

Hopcroft J., Motwani R., Ullman J. Introduction to Theory of Automata, Formal Languages and Computation. – Boston, AddisonWesley, 2006. – 535 p.

Refbacks

There are currently no refbacks.

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

ISSN: 2307-8162