Существуют ли CFG полиномиального размера, которые описывают этот конечный язык?

9

Есть ли перестановки π1,π2 и полиномиальный размер (в |w|=n) контекстно-бесплатная грамматика, описывающая конечный язык {wπ1(w)π2(w)} по алфавиту {0,1}?

ОБНОВЛЕНИЕ: для одной перестановки π это возможно. π является разворотом или относительно незначительной модификацией разворота.

jerr18
источник
5
Также спросил на math.stackexchange. Он имеет в виду: есть ли последовательность перестановок?π1n,π2nSn такой что языки Ln={wπ1(w)π2(w):w{0,1}n}имеют полиномиальный размер CFGs?
Юваль Фильмус
1
Знаем ли мы, что есть CFG для L=nLn?
Каве
4
@Kaveh: Ответ - нет, для любой последовательности завивки. Если ваш языкL были контекстно-свободны, то у него длина прокачки п, Примените лемму прокачки для CFG к строке в L, связанной свесзнак равно0п1п, Лемма прокачки для CFG также позволяет нам сказать, что, если OQ имеет положительный ответ, то CFG дляLN должен использовать по крайней мере Ω(N/журналN) переменные, так как нам нужно 3N быть меньше, чем длина накачки, так что наш CFG для LN не принимает строки длины >3N, Я пока не вижу, как использовать это, чтобы исключить положительный ответ на OQ, но это могло бы быть возможно.
Джошуа Грохов
1
@Kaveh: (Кроме того, если последовательность перми можно выбрать произвольно, то ваш язык Lдаже не нужно вычислять ... По-видимому, OQ неоднороден.)
Джошуа Грохов

Ответы:

13

Хомская нормальная форма

CFG находится в CNF (нормальная форма Хомского), если единственные производства имеют форму Aa а также AВС; грамматика может быть перенесена в CNF только с квадратичной раздувкой.

Для грамматики г в CNF у нас есть хорошая лемма подслов: еслиг генерирует слово весто для каждого весесть подслово Икс из вес длины /2|Икс|< который генерируется некоторым нетерминалом г, Доказательство: опуститесь (двоичное) синтаксическое дерево, всегда обращаясь к потомку, который генерирует более длинное подслово. Если вы начали с подсловом размера по крайней мере, ты не мог пойти ниже /2,

Решение

Без ограничения общности можно предположить, что грамматика для LN (такой язык с конкретными π1,π2SN) в нормальном состоянии. ЯзыкLN состоит из слов вес(Икс)знак равноИксπ1(Икс)π2(Икс) для всех Икс{0,1}N,

Используя лемму подслова, для каждого вес(Икс) мы можем найти подстроку s(Икс) длины

N2|s(Икс)|<N
генерируется каким-то символом A(Икс) и происходит в положении p(x),

Предположим, что p(x)=p(y) а также A(x)=A(y), поскольку|s(x)|<nПодслово s(x) не может пересекать оба x часть и π2(x) часть w(x); мы можем предположить, что это не пересекается сxчасть. таким образомw(x) имеет форму xαs(x)β, Это подразумевает, чтоA(x) генерирует ровно одну строку, а именно s(x), Следовательноs(x)=s(y),

Сейчас же s(y) пересекается либо π1(y) или π2(y) по крайней мере n/4 места, и, таким образом, определяет, по крайней мере, n/4 биты y, Поэтому самое большее23n/4 строки y{0,1}n может иметь p(x)=p(y) а также A(x)=A(y), Так как есть максимум3n возможности для p(y)мы получаем что есть хотя бы

2n/43n
разные нетерминалы в грамматике.

Комментарий: то же самое доказательство работает, если π1,π2S{0,1}nт.е. произвольные перестановки на множестве всех nслова. Данныйn/4 биты πi(y)Точно 23n/4 прообразы y,

Больше примеров

Используя тот же метод, можно доказать, что язык, где каждый символ появляется ровно дважды, требует CFG экспоненциального размера в размере алфавита. Мы можем заменить «дважды» на любое подмножествоN кроме четырех тривиальных (игнорируя 0либо не содержит ни одного из N1 или все это).

Я был бы признателен за ссылку на этот метод доказательства.

Юваль Фильмус
источник
2
Юваль, не могли бы вы также скопировать решение здесь.
Каве
Спасибо, Юваль. Если ваш метод является правильным и новым, я был бы рад прочитать статью, в которой исследуются более общие случаи с положительными или отрицательными результатами для полисайтовых CFG для конечных или бесконечных языков.
jerr18
3
Есть такая запись: cs.toronto.edu/~yuvalf/cfg.pdf .
Юваль Фильмус
Я предполагаю за исключением N1Вы имеете в виду «хотя бы одно вхождение терминала». Означает ли это, что вы можете генерировать все перестановки, пересекаяΣ|Σ|?
jerr18
1
См. Связанный вопрос cstheory.stackexchange.com/q/5014, где Юваль опубликовал ответ с опубликованной ссылкой.
Андрас Саламон