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.

up vote 25 down vote accepted

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:

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

  • 2
    Very interesting connection: The term growth rate is a well known one in group theory and heavily studied. However virtually free groups have exponential growth rate and we know by Muller and Schupp (1983) that word problems of virtually free groups are deterministic context-free. Do you know if there is further work about the growth rate of deterministic context-free languages? – datell Nov 14 at 16:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.