Growth and ergodicity of context-free languages II: The linear case

摘要

A language L over a finite alphabet Sigma is called growth-sensitive if forbidding any non-empty set F of subwords yields a sub-language L-F whose exponential growth rate is smaller than that of 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.