Número de palavras com comprimento n em um idioma sem contexto

por o número de palavras de comprimento em um idioma (possivelmente ambíguo) sem contexto. $w_n$ $n$

O que se sabe sobre ? $w_n$

Tenho certeza de que isso foi estudado muito, mas não consegui encontrar nada.

fl.formal-languages context-free domotorp
fonte

Existe um algoritmo randoimizado no tempo quase-polinomial para aproximar dentro de uma aproximação . sciencedirect.com/science/article/pii/S0890540197926213

w_{n}

$w_n$

(1 + ϵ)

$(1+\epsilon)$

Chandra Chekuri

Para CFLs não ambíguas, o teorema clássico de enumeração de Chomsky-Schützenberger deve ser interessante.

Martin Berger

Respostas:

Toda linguagem livre de contexto tem crescimento polinomial ou crescimento exponencial. Na notação do questionador:

Existe um polinômio modo que para todos os $p$ $w_n\le p(n)$ $n$
Ou existe $c>1$ , de modo que $w_n\ge c^n$ para infinitamente muitos $n$ .

Isso foi mostrado, por exemplo, em:

Roberto Incitti:
"A função de crescimento de linguagens sem contexto"
Theoretical Computer Science 255 (2001), páginas 601-605

Martin R. Bridson, Robert H. Gilman:
"Linguagens sem Contexto de Crescimento Subexponencial"
Journal of Computer and System Sciences 64 (2002), páginas 308-310

E para uma dada gramática livre de contexto, pode-se decidir em tempo polinomial se a linguagem gerada tem crescimento polinomial ou exponencial:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Encontrando a taxa de crescimento de uma linguagem regular ou livre de contexto em tempo polinomial.
International Journal of Foundations of Computer Science 21 (2010), páginas 597-618

Gamow
fonte

Conexão muito interessante: O termo taxa de crescimento é bem conhecido na teoria dos grupos e muito estudado. No entanto, grupos virtualmente livres têm taxa de crescimento exponencial e sabemos por Muller e Schupp (1983) que os problemas de palavras de grupos virtualmente livres são determinísticos e livres de contexto. Você sabe se há mais trabalho sobre a taxa de crescimento de linguagens determinísticas livres de contexto?

dtell