Growth-sensitivity of context-free languages

AbstractA language L over a finite alphabet Σ is called growth-sensitive if forbidding any set of subwords F yields a sub-language LF whose exponential growth rate is smaller than that of L. It is shown that every (essentially) ergodic non-linear context-free language of convergent type is growth-sensitive. “Ergodic” means that the dependency di-graph of the generating context-free grammar is strongly connected, and “essentially ergodic” means that there is only one non-regular strong component in that graph. The methods combine (1) an algorithm for constructing from a given grammar one that generates the associated 2-block language and (2) a generating function technique regarding systems of algebraic equations. Furthermore, the algorithm of (1) preserves unambiguity as well as the number of non-regular strong components of the dependency di-graph