Growth and ergodicity of context-free languages II: The linear case
Tullio G. Ceccherini-Silberstein · Transactions of the American Mathematical Society · 2006
A language L L over a finite alphabet Σ \bf \Sigma is called growth-sensitive if forbidding any non-empty set F F of subwords yields a sub-language L F L^F whose exponential growth rate is smaller than that of L L . Say that a context-free grammar (and associated language) is ergodic if its dependency di-graph is strongly connected. It is known that regular and unambiguous non-linear context-free languages which are ergodic are growth-sensitive. In this note it is shown that ergodic unambiguous linear languags are growth-sensitive, closing the gap that remained open.