Lower bounds for context-free grammars

Ellul, Krawetz, Shallit and Wang prove an exponential lower bound on the size of any context-free grammar generating the language of all permutations over some alphabet. We generalize their method and obtain exponential lower bounds for many other languages, among them the set of all squares of given length, and the set of all words containing each symbol at most twice.

► We develop a simple method for proving lower bounds on the size of CFGs. ► The method combines a lemma on derivation trees with a simple counting argument. ► Simple applications: generating all permutations, generating all squares. ► Another application: languages defined by allowed symbol counts.