Length considerations in context-free languages

AbstractIn 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 Ginsburg (1966). 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 uviwxiy (Ilie, 1994). 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