[HN Gopher] How to enumerate trees from a context-free grammar
       ___________________________________________________________________
        
       How to enumerate trees from a context-free grammar
        
       Author : luu
       Score  : 35 points
       Date   : 2024-06-13 01:30 UTC (3 days ago)
        
 (HTM) web link (arxiv.org)
 (TXT) w3m dump (arxiv.org)
        
       | 082349872349872 wrote:
       | I prefer to enumerate via a shortlex variant, primary key being
       | number of leaves and secondary being the index of the particular
       | expansion.
        
         | CoastalCoder wrote:
         | Why the preference?
         | 
         | (For context, I'm completely new to this topic.)
        
           | 082349872349872 wrote:
           | Because I use them for testing, so I generally want to
           | uniformly generate samples within a particular size of tree.
           | 
           | (generating random trees the naive way tends to produce the
           | occasional huge tree amidst huge numbers of tiny trees)
        
             | gessha wrote:
             | If it's not confidential, what type of problem would
             | require manipulation and testing of trees?
        
       | bmc7505 wrote:
       | This is a very nice approach. Unfortunately, Piantadosi's pairing
       | function does not work for acyclic grammars (i.e., finite CFLs).
       | We found a variant that handles enumerating all trees of a
       | certain width from an arbitrary CFG, i.e., L(G) [?] S^n, or whose
       | language is finite [1]:
       | 
       | [1]:
       | https://github.com/breandan/galoisenne/blob/master/latex/laf...
        
       ___________________________________________________________________
       (page generated 2024-06-16 23:01 UTC)