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

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.