Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?
Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L n «должен» иметь размер Ω ( п ! ) . Таким образом, нас интересует асимптотический размер самых маленьких CFG для языков.
Подобные вопросы были рассмотрены в нескольких статьях:
- Чарикар и др. («Аппроксимация наименьшей грамматики: сложность Колмогорова в естественных моделях») рассмотрим, насколько трудно приблизиться к размеру наименьшего CFG, порождающего данное слово .
- Больше работы в этом направлении - Арпе и Рейщук, «О сложности оптимального сжатия на основе грамматики».
- У Питера Асвельда есть несколько работ на эту тему (например, «Генерация всех перестановок с помощью контекстно-свободных грамматик в нормальной форме Хомского»). Он пытается оптимизировать некоторые параметры на определенных типах грамматик, генерирующих множество всех перестановок, в частности нормальных форм Хомского и Грейбаха.
Существуют ли статьи, предоставляющие нижние оценки для размера контекстно-свободных грамматик для конкретных конечных языков?
reference-request
fl.formal-languages
lower-bounds
grammars
context-free
Юваль Фильмус
источник
источник
Ответы:
Добрый рецензент прислал мне бумагу, которая доказывает точно такую же нижнюю границу, как и я, точно таким же образом. Бумага
Результатом является теорема 30 в статье.
источник