On Pumping Constants and Smallest Grammars for Context-Free Languages
摘要
We study the relationship between the minimal context-free pumping constant of a context-free language and the size of the context-free grammar that generates it. For the size, we consider the sum of the lengths of the right-hand sides of the productions and the total number of symbols to write the productions, including the “ \(\rightarrow \) ” symbol in each production; the latter size concept is known in the literature as symbol complexity. We prove tight bounds for both size concepts. Furthermore, we apply our results to some open problems on the symbol complexity of languages. In particular, we show that for the language \(L_n=\{a^n\}\) the symbol complexity is at least \(6\log _4 n\) and at most \(6\log _4 n + O(\frac{\log n}{\log \log n})\) .