Continuing from prior work, explores grammar size and pumping constants for context-free languages in Greibach normal form, suggesting new insights.
We continue our research, started in [H. Gruber and M. Holzer. On pumping constants and smallest grammars for context-free languages, LNCS 15840, pp. 54–68, 2025], on the relation between context-free grammar size and minimal pumping constants w.r.t. Bar-Hillel’s pumping lemma, now considering the case when the language is described by a grammar in Greibach normal form.
No takes yet. Share an insight, caveat, or question.
Gruber et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: