Количество слов длины n в языке без контекста

Обозначим через количество слов длины в (возможно, неоднозначном) контекстно-свободном языке. $w_n$ $n$

Что известно о ? $w_n$

Я уверен, что это много изучалось, но я ничего не мог найти на нем.

fl.formal-languages context-free domotorp
источник

Существует квазиполиномиальный рандомизированный по времени алгоритм для аппроксимации с точностью до аппроксимации. sciencedirect.com/science/article/pii/S0890540197926213

w_{n}

$w_n$

(1 + ϵ)

$(1+\epsilon)$

Чандра Чекури

Для однозначных КЛЛ должна представлять интерес классическая теорема Хомского-Шютценбергера .

Мартин Бергер,

Ответы:

Каждый язык без контекста имеет полиномиальный или экспоненциальный рост. В обозначениях вопрос задается:

Либо есть многочлен так что для всех $p$ $w_n\le p(n)$ $n$
Или существует , так что для бесконечного числа . $c>1$ $w_n\ge c^n$ $n$

Это было показано, например, в:

Роберто Инчитти:
«Функция роста контекстно-свободных языков»
Теоретическая информатика 255 (2001), страницы 601-605

Мартин Р. Бридсон, Роберт Х. Гилман:
«Не зависящие от контекста языки субэкспоненциального роста»
Журнал компьютерных и системных наук 64 (2002), страницы 308-310

А для данной неконтекстной грамматики за полиномиальное время можно решить, имеет ли сгенерированный язык полиномиальный или экспоненциальный рост:

Павел Гавриховский, Даля Кригер, Нарад Рамперсад, Джеффри Шаллит:
«Нахождение скорости роста регулярного или контекстно-независимого языка в полиномиальное время.
Международный журнал основ информатики 21 (2010), страницы 597-618

Гамов
источник

Очень интересная связь: термин скорость роста хорошо известен в теории групп и хорошо изучен. Однако практически свободные группы имеют экспоненциальный темп роста, и мы знаем по Мюллеру и Шуппу (1983), что проблемы слов практически свободных групп не имеют детерминированного контекста. Знаете ли вы, есть ли дальнейшая работа о темпах роста детерминированных контекстно-свободных языков?

dtell