Scholarlink

<p>We continue our research, started in [H.&#xa0;Gruber and M.&#xa0;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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On pumping constants and smallest grammars for context-free languages. Part II—Greibach normal form

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月7日

查看全文
  • Hermann Gruber,
  • Markus Holzer

摘要

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.