On the Density of Regular and Context-Free Languages

The density of a language is defined as the function d(L)(n) = vertical bar L n L boolean AND Sigma(n)vertical bar and counts the number of words of a certain length accepted by L. The study of the density of regular and context-free languages has attracted some attention culminating in the fact that such languages are either sparse, when the density can be bounded by a polynomial, or dense otherwise. We show that for all nonambiguous context-free languages the number of accepted words of a given length n can also be computed recursively using a finite combination of the number of accepted words smaller than n, or d(L) = Sigma(k)(j=1) u(j)d(L)(n - j). This extends an old result by Chomsky and provides us with a more expressive description and new insights into possible applications of the density function for such languages as well as possible characterizations of the density of higher languages.