# Number of words of length n in a context-free language

Denote by $$w_n$$ the number of words of length $$n$$ in a (possibly ambiguous) context-free language.

What is known about $$w_n$$?

I'm sure this has been studied a lot, but I couldn't find anything at all on it.

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

• Either there is a polynomial $$p$$ so that $$w_n\le p(n)$$ for all $$n$$
• Or there exists a $$c>1$$, so that $$w_n\ge c^n$$ for infinitely many $$n$$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth: