LENGTH CONSIDERATIONS IN CONTEXT-FREE LANGUAGES

In this paper we investigate languages containing at most a bounded nu mber of words of each length. We first show that the context-free lang uages for which the number of words of every length is bounded by a ti red polynomial are exactly the bounded context-free languages in the s ense of Ginsburg (1966). Thus, we present a length characterization fo r bounded context-free languages. We then study slender context-free l anguages, i.e., those containing at most a constant number of words of each length. Recently, Ilie proved that every such language can be de scribed by a finite union of terms of the form uv(i)wx(i)y (Ilie, 1994 ). We provide a completely different proof of this, using constructive methods. This enables us to prove that thinness and slenderness are d ecidable. Our proofs are based upon a novel characterization of langua ges in terms of the structure of the infinite paths in their prefix cl osure. This characterization seems to be interesting in itself, and ca n be expanded to more general families of languages.