I present a simple algorithm for enumerating the trees generated by a Context Free Grammar (CFG). The algorithm uses a pairing function to form a bijection between CFG derivations and natural numbers, so that trees can be uniquely decoded from counting. This provides a general way to number expressions in natural logical languages, and potentially can be extended to other combinatorial problems. I also show how this algorithm may be generalized to more general forms of derivation, including analogs of Lempel-Ziv coding on trees.
翻译:我提出了一种简单的算法,用于枚举由上下文无关语法(CFG)生成的树。该算法使用配对函数将CFG派生和自然数形成双射,使得可以通过计数唯一地解码树。这提供了一种以自然逻辑语言中表达式编号的一般方法,并且可能可以扩展到其他组合问题。我还展示了如何将此算法推广到更一般的推导形式,包括树上的Lempel-Ziv编码模拟。