A Method for Constructing Combinatorial Generation Algorithms for Context-Free Languages Based on AND/OR Tree Structures

This paper considers the problem of constructing combinatorial generation algorithms for sets of discrete structures representing words of formal languages defined by context-free grammars. Existing combinatorial generation algorithms process only words of a given length from formal languages defined by context-free grammars, which is a limitation on their application. The main result of the study is the proposed method for constructing ranking and unranking algorithms, which is based on the mapping a given set onto a set of variants of the corresponding AND/OR tree. In comparison with existing analogues, the proposed method also allows processing both unambiguous and ambiguous context-free grammars. In addition, the use of the obtained unranking algorithms ensures uniform distribution of randomly generated words, but due to duplication of branches of the AND/OR tree, it is also possible to ensure non-uniform generation. At the same time, a distinctive feature of the obtained combinatorial generation algorithms is the ability to work with additional quantitative characteristics, which is absent in existing analogues. To confirm the performance of the proposed method, examples of constructing ranking and unranking algorithms for context-free languages according to the proposed method are presented. The ranking and unranking algorithms for context-free languages obtained using the proposed method can find their application in solving data compression problems and modeling objects described by words of such formal languages.