Greedy Grammar Induction with Indirect Negative Evidence

This paper proposes a non-lexicalized grammar-induction procedure that separates two tests: recognition of the observed finite presentation, and rejection of short preterminal strings generated by a hypothesis but unsupported by the evidence. The central object is the rule-coverage bound ${\mathrm{\ell }}^{\ast }(G)$: the maximum, over rules in $G$, of the length of the shortest preterminal string whose derivation uses that rule. This bound induces the comparison universe ${\mathrm{\Sigma }}_{\mathrm{p}\mathrm{r}\mathrm{e}}^{\le {\mathrm{\ell }}^{\ast }(G)}$, where unsupported generated strings serve as indirect evidence against overgenerating hypotheses. We give a greedy search algorithm over rule sets and prove a conditional weak-recovery theorem: under explicit reachability conditions and sufficient saturation of the presentation, the exact learner reaches a grammar weakly equivalent to the unknown target. The complexity analysis is slice-wise: for each fixed incrementality radius $k$, the search explores polynomially many rule-set extensions in the finite rule universe. Across 31 benchmark runs spanning Dyck-$k$ languages $(1\le k\le 4)$, palindromes, $a^n{b}^n$, English-like recursive fragments, and an inherently ambiguous union language, grammar-level analysis establishes weak equivalence between every returned grammar and its target.