Liczba słów o długości n w języku bezkontekstowym

Oznacz przez $w_n$ liczbę słów o długości $n$ w (możliwie niejednoznacznym) języku bezkontekstowym.

Co wiadomo o $w_n$ ?

Jestem pewien, że dużo się tego badano, ale nie mogłem w ogóle nic znaleźć.

fl.formal-languages context-free domotorp
źródło

Jest prawie wielomianem czas randoimized algorytm przybliżeniu

do w

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

w_{n}

$w_n$

(1 + ϵ)

$(1+\epsilon)$

Chandra Chekuri

W przypadku jednoznacznych świetlówek kompaktowych interesujące powinno być klasyczne twierdzenie Chomsky'ego-Schützenbergera .

Martin Berger

Odpowiedzi:

Każdy język bezkontekstowy ma albo wzrost wielomianowy, albo wzrost wykładniczy. W notacji pytania zadającego:

Albo istnieje wielomian $p$ więc $w_n\le p(n)$ dla wszystkich $n$
Lub istnieje $c>1$ , więc $w_n\ge c^n$ dla nieskończenie wielu $n$ .

Zostało to pokazane na przykład w:

Roberto Incitti:
„Funkcja wzrostu języków bezkontekstowych”
Teoretyczna informatyka 255 (2001), strony 601–605

Martin R. Bridson, Robert H. Gilman:
„Bezkontekstowe języki sub wykładniczego wzrostu”
Journal of Computer and System Sciences 64 (2002), strony 308–310

W przypadku gramatyki bezkontekstowej w czasie wielomianowym można zdecydować, czy generowany język ma wzrost wielomianowy czy wykładniczy:

Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
„Znajdowanie tempa wzrostu języka regularnego lub bezkontekstowego w czasie wielomianowym.
International Journal of Foundation of Computer Science 21 (2010), strony 597-618

Gamow
źródło

Bardzo interesujące powiązanie: Pojęcie tempa wzrostu jest dobrze znane w teorii grup i jest intensywnie badane. Jednak grupy praktycznie wolne mają wykładniczy wzrost, a Muller i Schupp (1983) wiemy, że problemy słowne grup praktycznie wolnych są deterministyczne i pozbawione kontekstu. Czy wiesz, czy są dalsze prace nad tempem wzrostu deterministycznych języków bezkontekstowych?

dtell