Jumlah kata dengan panjang n dalam bahasa bebas konteks

Dilambangkan dengan $w_n$ jumlah kata-kata panjang $n$ dalam (mungkin ambigu) bahasa bebas konteks.

Apa yang diketahui tentang $w_n$ ?

Saya yakin ini sudah banyak dipelajari, tetapi saya tidak dapat menemukan apa pun di dalamnya.

Setiap bahasa bebas konteks memiliki pertumbuhan polinomial atau pertumbuhan eksponensial. Dalam notasi dari pelamar pertanyaan:

• Entah ada polinomial $p$ sehingga $w_n\le p(n)$ untuk semua $n$
• Atau ada suatu $c>1$ , sehingga $w_n\ge c^n$ untuk tak terhingga banyaknya $n$ .

Ini telah ditunjukkan misalnya di:

Roberto Incitti:
"Fungsi pertumbuhan bahasa bebas konteks"
Theoretical Computer Science 255 (2001), Halaman 601-605

Martin R. Bridson, Robert H. Gilman:
"Bahasa Bebas Konteks Pertumbuhan Sub-eksponensial"
Jurnal Ilmu Komputer dan Sistem 64 (2002), Halaman 308-310

Dan untuk tata bahasa bebas konteks yang diberikan, seseorang dapat memutuskan dalam waktu polinomial apakah bahasa yang dihasilkan memiliki pertumbuhan polinomial atau eksponensial:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Menemukan Tingkat Pertumbuhan Bahasa Biasa atau Bebas Konteks dalam Waktu Polinomial.
Jurnal Internasional Yayasan Ilmu Komputer 21 (2010), Halaman 597-618