Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?
We can make the question more interesting by specifying a sequence of languages $L_n$, for example $L_n$ is the set of all permutations of $\{1,\ldots,n\}$: intuitively, a CFG for $L_n$ would "need" to have size $\Omega(n!)$. So we're interested in the asymptotic size of the smallest CFGs for the languages.
Similar questions have been dealt with in several papers:
- Charikar et al. ("Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models") consider how difficult it is to approximate the size of the smallest CFG generating a given word.
- More work in that direction is Arpe and Reischuk, "On the Complexity of Optimal Grammar-Based Compression".
- Peter Asveld has several papers on the subject (e.g. "Generating All Permutations by Context-Free Grammars in Chomsky Normal Form"). He's trying to optimize some parameters on specific types of grammars generating the set of all permutations, specifically Chomsky and Greibach normal forms.
However, so far I haven't been able to find any paper trying to prove a bound of $\Omega(n!)$ on the size of a CFG generating $L_n$.
Are there papers providing lower bounds for the size of context-free grammars for specific finite languages?
In response to several questions on this site as well as on math.stackexchange, I came up with a simple method able to prove exponential lower bounds on CFGs for specific languages, for example $L_n$. Are these results new? I find that hard to believe, and I'll be glad to get any literature pointers.
