Growth-sensitivity of context-free languages

✍ Scribed by Tullio Ceccherini-Silberstein; Wolfgang Woess

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 265 KB
• Volume: 307
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00095-1

✦ Synopsis

A language L over a ÿnite alphabet is called growth-sensitive if forbidding any set of subwords F yields a sub-language L F 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.