Growth and ergodicity of context-free languages
Tullio G. Ceccherini-Silberstein, Wolfgang Woess · Transactions of the American Mathematical Society · 2002
A language L L over a finite alphabet Σ \boldsymbol \Sigma is called growth-sensitive if forbidding any set of subwords F F yields a sublanguage L F L^{F} whose exponential growth rate is smaller than that of L L . It is shown that every ergodic unambiguous, nonlinear context-free language is growth-sensitive. “Ergodic” means for a context-free grammar and language that its dependency di-graph is strongly connected. The same result as above holds for the larger class of essentially ergodic context-free languages, and if growth is considered with respect to the ambiguity degrees, then the assumption of unambiguity may be dropped. The methods combine a construction of grammars for 2 2 -block languages with a generating function technique regarding systems of algebraic equations.