### Eight variants of finite automata for checking the fulfillment of the coverage relation of iterations of two finite languages. Part I

#### Abstract

The task for which all automata of this paper are considered is to describe algorithms for checking the so-called binary coverage relation, which was considered in many of our previous papers: it is performed for two nonempty finite languages if and only if any iteration of words of the first language is a prefix of some iteration of words of the second language. This task can be viewed from several different points of view, which was done in previous works.

In this paper, we are primarily interested in various variants for implementing algorithms to verify the fulfillment of this relationship, and more specifically, the use of finite automata for such algorithms. 2 variants of such automata have already been previously described in our previous works, and in this paper we add 6 more variants to them. The main purpose of considering several automataalgorithms is as follows. Earlier, we described a polynomial algorithm for constructing one of these automata. However, the existence of such a polynomial algorithm does not mean that we can check the fulfillment of the condition we need in a polynomial way, due to the following circumstance. If we build a nondeterministic automaton to answer the question in the same way as we described earlier, then for a positive answer. it must accept any word of the universal language; the last condition cannot be checked in polynomial time. However, we also cannot say that such a polynomial algorithm does not exist: additional research is needed. Therefore, the presence of four descriptions of nondeterministic automata that answer the question about the fulfillment of the considered binary relation will give some new opportunities to search for a possible algorithm that checks the main condition of the paper in polynomial time. 8 variants of the automata considered in the paper are naturally obtained using three different dichotomies: one of them is the “usual” one (whether the automaton is deterministic), and the other two dichotomies are directly related to the issues of checking the implementation of the binary coverage relation considered in the paper. Specifically, these two dichotomies are as follows: first, which of the two finite languages under consideration is the “main” one (it is that for which we apply the basic morphism to check); secondly, do we consider the required covers of each iteration word directly when it occurs, or not immediately, but after the formation of some auxiliary language. In the presented first part of this paper, we briefly describe all the necessary dichotomies, give the associated auxiliary designations, and also give new versions of the formulations of the two automata considered in previous papers.

#### Full Text:

PDF (Russian)#### References

Melnikov B.F., Korabelshchikova S.Yu., Dolgov V.N. On the task of extracting the root from the language // International Journal of Open Information Technologies. 2019. Vol. 7, No. 3. P. 1–6.

B Melnikov, A Melnikova. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I, International Journal of Open Information Technologies, 2021, 9(4): 1–11 (in Russian).

B Melnikov, A Melnikova. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II, International Journal of Open Information Technologies, 2021, 9(5): 1–11 (in Russian).

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

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

B Melnikov, A Melnikova. A polynomial algorithm for constructing a finite automaton to check the equality of infinite iterations of two finite languages, International Journal of Open Information Technologies, 2021, 9(11): 1–10 (in Russian).

B Melnikov. 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, 10(4): 1–9 (in Russian).

B Melnikov. 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, 10(5): 1–8 (in Russian).

B Melnikov. 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, 10(7): 1–9 (in Russian).

Meng Lingqian, Melnikov B.F. About the groupoid of the primary automaton PRI defined for one finite language // International Journal of Open Information Technologies. 2023. Vol. 11, No. 9. P. 1–12 (in Russian).

Melnikov B.F. The equality condition for infinite catenations of two sets of finite words // International Journal of of Foundations of Computer Science. 1993. Vol. 4, No. 3. P. 267–273.

Melnikov B.F., Melnikova A.A. Some more on ω-finite automata and ω-regular languages. Part I: The main definitions and properties // International Journal of Open Information Technologies. 2020. Vol. 8, No. 8. P. 1–7.

A Aho, J Hopcroft, J Ullman. The Design and Analysis of Computer Algorithms, Addison-Wesley, Massachusetts, 1974. – 470 p.

B Melnikov. On the complex of problems for the study of the necessary conditions for the equality of infinite iterations of finite languages, International Journal of Open Information Technologies, 2023, 11(1): 1–12 (in Russian).

Melnikov B.F., Melnikova A.A. Application of petal finite automata to verify the fulfillment of a special case of the Zyu hypothesis (for a given finite language) // International Journal of Open Information Technologies. 2023, 11(3): 1–11 (in Russian).

Melnikov B.F., Melnikova A.A. On the problems of extracting the root from a given finite language // International Journal of Open Information Technologies. 2023. Vol. 11, No. 5. P. 1–14 (in Russian).

### Refbacks

- There are currently no refbacks.

Abava Кибербезопасность IT congress 2023

ISSN: 2307-8162