1 of 4
Gamow
• 5.7k
• 6
• 21
• 38

Every context-free language has either polynomial growth or polynomial 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:

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

Gamow
• 5.7k
• 6
• 21
• 38