Publication date
December 1981
DOI Publisher
Published by Elsevier B.V. ISSN
0304-3975 Citation count (estimate)
8Abstract
AbstractIn this note we answer an open question in the theory of grammatical complexity: We show that if L is an infinite context-free language, then Ln, the set of words in L of length less than or equal to n can be generated by O(|Ln|2/3) context-free productions, and if L is an infinite linear language, then Ln can be generated by O(√|Ln|) linear productions. We also show that these bounds are the best possible
Add to ORKG