Coverage Relation for Iterations of Finite Languages: An Algorithm for Obtaining All the Defining Automata

Earlier, we considered special binary relations in a set of finite formal languages. It is of interest to study equivalence classes in one of the binary relations under consideration, specifically in the equivalence relation. The algorithmic problems that arise here are also interesting, for example, the construction of an optimal inverse morphism. This article discusses one of these algorithmic problems. Previously, for algorithms for determining the fulfillment of one of the binary relations under consideration, we used finite automata; 8 variants of such finite automata were described. These automata are built on the basis of inputs, which are two finite languages, for which the automata check the possible fulfillment of a binary relationship. However, it is possible to simplify the automata under consideration (which are actually algorithms) and come to consider an algebraic object on the basis of which any of these automata can be constructed. Such an object, depending not on 2 inputs (languages), but on one, is considered in this article. This is not a finite automaton, but a groupoid (in many special cases, it is a semigroup and even a monoid), and, as already mentioned, any of the finite automata with a fixed second language can be obtained from it.