Semilattice of roots from formal languages of a special kind

Svetlana Korabelshchikova


This article presents the result of studying the structure of a set of roots from languages of a special type, namely containing all possible words of length from t1 to t2 (t£ t2). The General case of extraction of n-th degree roots from a given language is studied; algorithms for finding all roots from the language, primitive roots, as well as the results of the programs that implement the proposed algorithms are given.

The problem under consideration is reduced to the problem of the backpack and is solved by the method of software implementation of the proposed algorithms. On the set of roots from the language, the order relation is set, the minimum and maximum elements are defined. The paper shows that the set of roots from languages of a special type is either empty or forms an upper semilattice, the minimum elements of which are the primitive roots, and the maximum element is the trivial root from the given language.

There are clear simple examples that illustrate the ambiguity of the operation of extracting a root from a language, the relationship between sets of roots from two languages with equally cardinal number of index sets, the properties of primitive roots, and the structure of the semilattice of roots. The results obtained can be used for a compact description of sets of roots and similar sets, as well as for their quantitative estimates.

Full Text:

PDF (Russian)


Melnikov B., Vylitok A., Melnikova E. Iterations of languages and finite automata. International Journal of Open Information Technologies, 2017, vol. 5, № 12, pp. 1–7.

Melnikov B. Extended nondeterministic finite automata.

Fundamental Informatics, 2010, vol. 104, № 3, pp. 255–265.

Melnikov B. The equality condition for infinite catenations of two sets of finite words. International Journal of Foundations of Computer Science, 1993, vol. 4, № 3, pp. 267–273.

Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages. Informatics, 2000, vol. 11, № 4, pp. 441–446.

Korabel'shchikova S., Melnikov B. Iterations of languages and maximal prefix codes. Bulletin of the Voronezh State University. Series: Physics. Mathematics, 2015, № 2, pp. 106–120.

Korabel'shchikova S., Melnikov B. Maximal prefix codes and subclasses of the context-free languages class. Bulletin of the Northern (Arctic) Federal University. Series: Natural sciences, 2015, № 1, pp. 121–129.

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, № 3, pp. 1–6.

Korabelschikova S.Yu., Chesnokov A.I., Tutygin A.G. About primitive roots from languages of a special kind. Proceedings of the IX international conference "Discrete models in the theory of control systems", 2015, pp. 116–118.

Krevsky I. G., Seliverstov M. N., Grigorieva K. V. Formal languages, grammars and bases of construction of translators: a Textbook / ed. by A. M. Bershadsky. Penza: Publishing house of Penza State University, 2002, 124 p.

Birkhoff G. Theory of lattices. Moscow: Publishing house Science, 1984, 566 p.


  • There are currently no refbacks.

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

ISSN: 2307-8162