On lengths of words in context-free languages

✍ Scribed by Lucian Ilie

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 292 KB
• Volume: 242
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00266-7

✦ Synopsis

We consider slender languages, that is, languages for which the number of words of the same length is bounded from above by a constant. It is known that the slender context-free languages are precisely the unions of paired loops, that is, ÿnite unions of sets of the form {uv n wx n y | n¿0}. Analysing the structure of the derivation trees of such loops, we ÿnd some upper bounds for the lengths of words in the loops of a slender context-free language, i.e., the words u; v; w; x; y in the notation above. These upper bounds depend on the given language only. Using this result, we give two new and simple proofs for the decidability of the slenderness problem for context-free languages. Moreover, due to the constructivity of our proof, we are able to ÿnd e ectively a representation as union of paired loops for an arbitrary slender context-free language; even a representation as a disjoint such union. As a consequence, we prove that the maximal number of words of the same length is computable. Finally, some undecidable problems are investigated.