Length considerations in context-free languages

✍ Scribed by Danny Raz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 905 KB
• Volume: 183
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00308-8

✦ Synopsis

In this paper we investigate languages containing at most a bounded number of words of each length. We first show that the context-free languages for which the number of words of every length is bounded by a fixed polynomial are exactly the bounded context-free languages in the sense of . Thus, we present a length characterization for bounded context-free languages. We then study slender context-free languages, i.e., those containing at most a constant number of words of each length. Recently, Ilie proved that every such language can be described by a finite union of terms of the form UV'WX'~ . We provide a completely different proof of this, using constructive methods. This enables us to prove that thinness and slenderness are decidable. Our proofs are based upon a novel characterization of languages in terms of the structure of the infinite paths in their prefix closure. This characterization seems to be interesting in itself, and can be expanded to more general families of languages.