The use of petal finite automata to verify the fulfillment of a special case of the Zyu hypothesis (for a given finite language)

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we continue to study the properties of a special binary equivalence relation at infinity. Before, we described one hypothesis of the theory of formal languages, which we called the Zyu hypothesis; one of some its equivalent formulations can be expressed as follows. For two finite languages A and B without empty words, we can write the necessary and sufficient condition that the iteration of any of these languages belongs to the set of prefixes of the second language as follows: there is some alphabet (different from the alphabet over which A and B are given), over it there are two certain maximal prefix codes (generally speaking, different ones) and two languages containing these maximal prefix codes as subsets, as well as some morphism between the two considered alphabets. Then, applying this morphism to the last two languages, we obtain the given languages A and B. We consider an equivalent formulation of this hypothesis using not two languages over the given alphabet, but only one; at the same time, it is important to note that such a variant of the Zyu hypothesis consists in fulfilling some condition for any finite language. Using the above formulation, the subject of this article can be briefly described as follows: how can a similar version of the Zyu hypothesis be tested not for any finite language, but for one given specific language A. At the same time, we do not strive for the polynomial algorithm of such a check: such a polynomiality would follow also the polynomiality of the verification algorithm of equivalence languages of two given nondeterministic finite automata. The paper presents the formulations of a variant of the Zyu hypothesis using a petal nondeterministic automaton constructed according to some given finite language A. After that, the formulation of another variant of this hypothesis is given; it uses a canonical automaton equivalent to such a petal automaton. All variants of the hypothesis are illustrated by examples in which the same language is considered; at the same time, certainly, the examples are given only for one language, while hypotheses are formulated for the whole set of finite languages


Full Text:

PDF (Russian)

References


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

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

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. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.

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

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

Melnikov B. Algorithm for checking equality of infinite iterations of finite languages // Bulletin of the Moscow University. Series 15: Computational Mathematics and Cybernetics. – 1996. – No. 4. – P. 49–56 (in Russian).

Melnikov B. 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.

Lallement G. Semigroups and Combinatorial Applications. – NJ, Wiley & Sons, Inc. – 1979. – 376 p.

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

Melnikov B. Subclasses of the context-free languages class (monograph). – Moscow, Moscow State University Ed. – 1995. – 174 p. – ISBN 5-211-03448-1 (in Russian).

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

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., Dolgov V. Simplified regular languages and a special equivalence relation on the class of regular languages. Part II // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 1. – P. 13–19 (in Russian).


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162