Número de palabras de longitud n en un lenguaje sin contexto

con el número de palabras de longitud en un lenguaje (posiblemente ambiguo) libre de contexto. $w_n$ $n$

¿Qué se sabe sobre ? $w_n$

Estoy seguro de que esto se ha estudiado mucho, pero no pude encontrar nada en él.

fl.formal-languages context-free domotorp
fuente

Existe un algoritmo randoimizado de tiempo cuasi polinomial para aproximar dentro de una aproximación . sciencedirect.com/science/article/pii/S0890540197926213

w_{n}

$w_n$

(1 + ϵ)

$(1+\epsilon)$

Chandra Chekuri

Para CFL sin ambigüedades, el teorema clásico de enumeración de Chomsky-Schützenberger debería ser de interés.

Martin Berger

Respuestas:

Todo lenguaje sin contexto tiene crecimiento polinómico o crecimiento exponencial. En la notación de la pregunta planteada:

O bien hay un polinomio para que para todo $p$ $w_n\le p(n)$ $n$
O existe un , de modo que para infinitamente . $c>1$ $w_n\ge c^n$ $n$

Esto se ha demostrado, por ejemplo, en:

Roberto Incitti:
"La función de crecimiento de los lenguajes sin contexto"
Theoretical Computer Science 255 (2001), páginas 601-605

Martin R. Bridson, Robert H. Gilman:
"Lenguajes sin contexto de crecimiento sub-exponencial"
Journal of Computer and System Sciences 64 (2002), páginas 308-310

Y para una gramática libre de contexto dada, uno puede decidir en tiempo polinómico si el lenguaje generado tiene un crecimiento polinómico o exponencial:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Encontrar la tasa de crecimiento de un lenguaje regular o sin contexto en tiempo polinómico.
Revista Internacional de Fundaciones de Ciencias de la Computación 21 (2010), páginas 597-618

Gamow
fuente

Conexión muy interesante: el término tasa de crecimiento es bien conocido en la teoría de grupos y está muy estudiado. Sin embargo, los grupos virtualmente libres tienen una tasa de crecimiento exponencial y sabemos por Muller y Schupp (1983) que los problemas verbales de los grupos virtualmente libres están libres de contexto determinista. ¿Sabes si hay más trabajo sobre la tasa de crecimiento de los lenguajes deterministas sin contexto?

Dtell