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

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 II, we continue to consider the properties of the relation S, which are significantly more complicated than ones considered in Part I. Among other things, we present variants of the application of the parallel letter in some problems of the theory of formal languages.


Full Text:

PDF (Russian)

References


Melnikov B., Dolgov V. Simplified regular languages and a special equivalence relation on the class of regular languages. Part I // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 9. – P. 12–20 (in Russian).

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

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. 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. 9. – P. 1–11 (in Russian).

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

Melnikov B., Vakhitova A. Some more on the finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Computational and Applied Mathematics). – 1998. – Vol. 5, No. 3. – P. 495–505.

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).

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


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2022

ISSN: 2307-8162