CFG Tree Enumeration: Simple Integer-Based Bijections

Table of Links

Abstract and 1. Introduction

2. Pairing functions

3. Enumerating trees
4. LZ-trees
5. Conclusion and References

3 Enumerating trees

Without loss of generality, we make two further assumptions about G:

(i) For each v ∈ V , the set of trees that v can expand to is infinite. Note that any non-finite context-free language G can be converted into this format by, for instance, taking any v ∈ V which only expands to finitely many trees, giving each tree a unique terminal symbol, and then removing v from the grammar. This will create a new grammar G’ whose productions can be translated back and forth to those of G with appropriate transformation of the new terminal symbols.

(ii) The rule ordering in G must be such that choosing the first (zeroth) rule for each nonterminal will eventually yield a terminal. This ensures that the first (0’th) item in any enumeration is a finite tree.

In this listing, we have assumed that cfg is a dictionary from nonterminal string symbols to lists of rules obeying (i) and (ii). In this algorithm, assumption (i) guarantees that any value of n can be converted into a tree. Assumption (ii) ensures that when n is zero, the algorithm will halt. Note that in both the mod and Rosenberg-Strong pairing functions, a value of 0 will be unpaired into two zeros. This means that generally, at some point in the algorithm, the call to from_int will take zero as an argument, and so (ii) is required to ensure that, in this case, it returns a finite tree rather than running forever.

An implementation of this algorithm is provided in the author’s library github[2] which is distributed under GPL. As an example, Figure 2 shows expansions from a simple CFG that one

might find in a natural language processing textbook:

Note that this encoding is a bijection between trees and integers, though not necessarily between terminals strings (yields) and integers, due to ambiguity in the grammar. Any number specifies a unique derivation, and vice-versa, giving rise to the bijection between trees and integers. The key assumption of this algorithm is context-freeness since that allows the pairings for each child of the tree to be independently expanded. However, a similar approach may be amenable to other combinatorial problems.

[2] Available at https://github.com/piantado/enumerateCFG