Limiting the Number of Possible CFG Derivative Trees During Grammar Induction with Catalan Numbers

Grammar induction runs into a serious problem due to the exponential growth of the number of possible derivation trees as sentence length increases, which makes unsupervised parsing both computationally demanding and highly indeterminate. This paper proposes a mathematics-based approach that alleviates this combinatorial complexity by introducing structural constraints based on Catalan and Fuss–Catalan numbers. By limiting the depth of the tree, the degree of branching and the form of derivation, the method significantly narrows the search space, while retaining the full generative power of context-free grammars. A filtering algorithm guided by Catalan structures is developed that incorporates these combinatorial constraints directly into the execution process, with formal analysis showing that the search complexity, under realistic assumptions about depth and richness, decreases from exponential to approximately polynomial. Experimental results on synthetic and natural-language datasets show that the Catalan-constrained model reduces candidate derivation trees by approximately 60%, improves F1 accuracy over unconstrained and depth-bounded baselines, and nearly halves average parsing time. Qualitative evaluation further indicates that the induced grammars exhibit more balanced and linguistically plausible structures. These findings demonstrate that Catalan-based structural constraints provide an elegant and effective mechanism for controlling ambiguity in grammar induction, bridging formal combinatorics with practical syntactic learning.