Anzahl der Wörter der Länge n in einer kontextfreien Sprache

Bezeichnen Sie mit die Anzahl der Wörter der Länge in einer (möglicherweise mehrdeutigen) kontextfreien Sprache. $w_n$ $n$

Was ist über ? $w_n$

Ich bin sicher, dass dies viel studiert wurde, aber ich konnte überhaupt nichts darauf finden.

fl.formal-languages context-free domotorp
quelle

Es gibt einen quasi-polynomial zeitlich optimierten Algorithmus, um auf eine -Näherung zu approximieren. sciencedirect.com/science/article/pii/S0890540197926213

w_{n}

$w_n$

(1 + ϵ)

$(1+\epsilon)$

Chandra Chekuri

Für eindeutige CFLs sollte der klassische Chomsky-Schützenberger-Aufzählungssatz von Interesse sein.

Martin Berger

Antworten:

Jede kontextfreie Sprache hat entweder ein polynomisches oder ein exponentielles Wachstum. In der Notation des Fragestellers:

Entweder gibt es ein Polynom $p$ so dass $w_n\le p(n)$ für alle $n$
Oder es gibt ein $c>1$ , so dass $w_n\ge c^n$ für unendlich viele $n$ .

Dies wurde zum Beispiel gezeigt in:

Roberto Incitti:
"Die Wachstumsfunktion kontextfreier Sprachen"
Theoretical Computer Science 255 (2001), S. 601-605

Martin R. Bridson, Robert H. Gilman:
"Kontextfreie Sprachen des subexponentiellen Wachstums"
Journal of Computer and System Sciences 64 (2002), S. 308-310

Und für eine gegebene kontextfreie Grammatik kann man in polynomieller Zeit entscheiden, ob die erzeugte Sprache polynomiell oder exponentiell wächst:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
" Ermitteln der Wachstumsrate einer regulären oder kontextfreien Sprache in polynomieller Zeit.
International Journal of Foundations of Computer Science 21 (2010), S. 597-618

Gamow
quelle

Sehr interessanter Zusammenhang: Der Begriff Wachstumsrate ist in der Gruppentheorie wohlbekannt und stark untersucht. Praktisch freie Gruppen weisen jedoch eine exponentielle Wachstumsrate auf, und wir wissen von Müller und Schupp (1983), dass Wortprobleme von praktisch freien Gruppen deterministisch kontextfrei sind. Wissen Sie, ob weitere Arbeiten zur Wachstumsrate deterministischer kontextfreier Sprachen vorliegen?

14.