Есть ли перестановки и полиномиальный размер (в ) контекстно-бесплатная грамматика, описывающая конечный язык по алфавиту ?
ОБНОВЛЕНИЕ: для одной перестановки это возможно. является разворотом или относительно незначительной модификацией разворота.
Есть ли перестановки и полиномиальный размер (в ) контекстно-бесплатная грамматика, описывающая конечный язык по алфавиту ?
ОБНОВЛЕНИЕ: для одной перестановки это возможно. является разворотом или относительно незначительной модификацией разворота.
Ответы:
Хомская нормальная форма
CFG находится в CNF (нормальная форма Хомского), если единственные производства имеют формуА → а а также A → B C ; грамматика может быть перенесена в CNF только с квадратичной раздувкой.
Для грамматикиг в CNF у нас есть хорошая лемма подслов: еслиг генерирует слово вес то для каждого л & le ; ш есть подслово Икс из вес длины ℓ / 2 ≤ | х | < ℓ который генерируется некоторым нетерминалом г , Доказательство: опуститесь (двоичное) синтаксическое дерево, всегда обращаясь к потомку, который генерирует более длинное подслово. Если вы начали с подсловом размера по крайней мереℓ , ты не мог пойти ниже ℓ / 2 ,
Решение
Без ограничения общности можно предположить, что грамматика дляLN (такой язык с конкретными π1,π2∈SN ) в нормальном состоянии. ЯзыкLN состоит из слов w ( x ) = xπ1( х )π2( х ) для всех x ∈ { 0 , 1}N ,
Используя лемму подслова, для каждогош ( х ) мы можем найти подстроку с ( х ) длины
Предположим, что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) мы получаем что есть хотя бы
Комментарий: то же самое доказательство работает, еслиπ1,π2∈S{0,1}n т.е. произвольные перестановки на множестве всех n слова. Данныйn/4 биты πi(y) Точно 23n/4 прообразы y ,
Больше примеров
Используя тот же метод, можно доказать, что язык, где каждый символ появляется ровно дважды, требует CFG экспоненциального размера в размере алфавита. Мы можем заменить «дважды» на любое подмножествоN кроме четырех тривиальных (игнорируя 0 либо не содержит ни одного из N≥1 или все это).
Я был бы признателен за ссылку на этот метод доказательства.
источник