Growth and ergodicity of context-free languages

摘要

A language L over a finite alphabet Sigma is called growth-sensitive if forbidding any set of subwords F yields a sublanguage L-F whose exponential growth rate is smaller than that of 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-block languages with a generating function technique regarding systems of algebraic equations. [References: 39]