Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2. Pairing functions 2. Pairing functions Enumerating trees
LZ-trees
Conclusion and References Enumerating trees Enumerating trees LZ-trees LZ-trees Conclusion and References 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. Author:
(1) Steven T. Piantadosi. Author: Author: (1) Steven T. Piantadosi. This paper is available on arxiv under CC BY 4.0 license. This paper is available on arxiv under CC BY 4.0 license. available on arxiv available on arxiv [2] Available at https://github.com/piantado/enumerateCFG

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

CFG Tree Enumeration: Simple Integer-Based Bijections

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

CFG Tree Enumeration: A Simple Integer-Based Bijection Algorithm

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

CFG Tree Enumeration: A Simple Integer-Based Bijection Algorithm

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps