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.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:
This has been shown for instance in:
"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:
Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618