Nombre de mots de longueur n dans une langue sans contexte

Notons $w_n$ le nombre de mots de longueur $n$ dans une langue sans contexte (éventuellement ambiguë).

Que sait-on de $w_n$ ?

Je suis sûr que cela a été beaucoup étudié, mais je n'ai rien trouvé du tout là-dessus.

fl.formal-languages context-free domotorp
la source

Il existe un algorithme quasi-polynomial à temps aléatoire pour approximer

à l'intérieur d'une approximation

. sciencedirect.com/science/article/pii/S0890540197926213

w_{n}

$w_n$

(1 + ϵ)

$(1+\epsilon)$

Chandra Chekuri

Pour les LFC sans ambiguïté, le théorème d'énumération Chomsky-Schützenberger classique devrait être intéressant.

Martin Berger

Réponses:

Chaque langue sans contexte a une croissance polynomiale ou une croissance exponentielle. Dans la notation de la question poser:

Soit il existe un polynôme $p$ sorte que $w_n\le p(n)$ pour tout $n$
Ou il existe un $c>1$ , de sorte que $w_n\ge c^n$ pour une infinité de $n$ .

Cela a été montré par exemple dans:

Roberto Incitti:
"La fonction de croissance des langages sans contexte"
Théorie informatique 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

Et pour une grammaire sans contexte donnée, on peut décider en temps polynomial si le langage généré a une croissance polynomiale ou exponentielle:

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

Gamow
la source

Lien très intéressant: Le terme taux de croissance est un terme bien connu dans la théorie des groupes et très étudié. Cependant, les groupes virtuellement libres ont un taux de croissance exponentiel et nous savons par Muller et Schupp (1983) que les problèmes de mots des groupes virtuellement libres sont sans contexte déterministe. Savez-vous s'il existe des travaux supplémentaires sur le taux de croissance des langues déterministes sans contexte?

dtell