Является ли дополнение {www | …} Без контекста?

12

Хорошо известно, что дополнение к зависит от контекста. Но как насчет дополнения ?{wwwΣ}{wwwwΣ}

domotorp
источник
1
Я обнаружил, что это теорема 4 в P. Dömösi, S. Horváth, M. Ito, L. Kaszonyi, M. Katsura: Формальные языки, состоящие из примитивных слов. link.springer.com/chapter/10.1007/3-540-57163-9_15
domotorp

Ответы:

11

Все-таки КЛЛ, полагаю, с адаптацией классического доказательства. Вот эскиз.

Рассмотрим , являющийся дополнением к , со словами длиной не mod удалено.L={xyz:|x|=|y|=|z|(xyyz)}{www}03

Пусть . Ясно, что - это CFL, так как вы можете угадать позицию и считать, что заканчивает после этого. Покажем, что .L={uv:|u|3|v|30u2|u|/3v|v|/3}Lpup/2L=L

  • LL : Пусть . Предположим, что есть такое , что . Затем напишите для первых символов , а для остальных. Естественно, . Теперь, что такое ? Первый: w=xyzLpxpypu3p/2wvu2|u|/3=xpv|v|/3

|v|/3=(|w|3p/2)/3=|w|/3p/2.

Следовательно, в это позиция: или, другими словами, позиция в . Это показывает, что .w

|u|+|v|/3=3p/2+|w|/3p/2=|w|/3+p,
pyu2|u|/3=xpyp=v|v|/3

Если , то пусть будет первыми символами , так что равно ; это остальная часть . Тогда: следовательно, аналогично, .ypzpu32(|w|/3+p)wu2|u|/3ypvw

|u|+|v|/3=2|w|/3+p
v|v|/3=zp

  • LL : мы отменяем предыдущий процесс. Пусть . Напишите . Тогда: Таким образом, и (поскольку, если имеет вид , он должен держать, что для всех ).w=uvLp=2|u|/3
    п+|вес|/3знак равно2|U|/3+|Uv|/3знак равно|U|+|v|/3.
    wp=u2|u|/3v|v|/3=wp+|w|/3wLwxxxwp=wp+|w|/3p
Михаэль Кадилхак
источник
2
Вау, невероятно! Я не утверждаю, что следовал каждой детали вашего аргумента, как будто я не понимаю, что вы подразумеваете под последней строкой («За последний бит»), или почему вы не отделяете случай, когда , но ваше решение в конце концов работает. Я бы суммировал основной трюк как . Подобный трюк также работает для дополнения любого . Интересно, будет ли зависит от контекста или нет. 3 a + 3 b = 2 a + ( b - a ) + 2 a + 2 b L r = { w r } L = { x y z : | х | = | у | = | z | ( х у )|w|/3<p/23a+3b=2a+(ba)+2a+2bLr={wr}L={xyz:|x|=|y|=|z|(xy)}
domotorp
1
@domotorp: Ура! Хорошо, «последний бит» не нужен, спасибо! Что касается «случая, когда », я не уверен, где вы это имеете в виду. Я что-то пропустил? Что касается вашего , я удивляюсь тому же, делая это "доказательство"! Пока не уверен :)L |w|/3<p/2L
Микаэль Кадилхак
2
О, мой плохой, всегда справедливо! p/2|w|/3
domotorp
Возможно, это не проблема, но может быть нечетным, поэтому вы должны разобраться со случаями Когда нечетно. | ты | = 3 р / 2 ( ? ) Рp|u|=3p/2(?)p
Марцио де
@MarzioDeBiasi: Да, именно поэтому это эскиз :-)
Михаэль Кадилхак,
10

Вот как я думаю о решении этой проблемы с помощью КПК. На мой взгляд, это интуитивно понятнее.

Слово не имеет формы если (i) (мод 3), который легко проверить, или (ii) существует некоторый входной символ который отличается от соответствующего символа который встречаетсяпозиции позже. xwww|x|0ab|w|

Мы используем обычный прием использования стека, чтобы поддерживать целое число , имея новый символ «дна стека» , сохраняя абсолютное значениев качестве количества счетчиков в стеке и sgn ( ) в зависимости от состояния КПК. Таким образом, мы можем увеличить или уменьшить , выполнив соответствующую операцию.tZ|t|tt

Цель состоит в том, чтобы использовать недетерминизм, чтобы угадать позиции двух сравниваемых символов, и использовать стек для записи , где - расстояние между этими двумя символами. t:=|x|3dd

Мы выполняем это следующим образом: увеличиваем для каждого видимого символа, пока не будет выбран первый угаданный символ , и записываем в состояние. Для каждого последующего входного символа, пока вы не решите, что видели , уменьшите на ( для длины ввода и для расстояния). Угадайте положение второго символа и запишите, ли . Продолжайте увеличивать для последующих входных символов. Принять, если (определяется по сверху) и .taabt213babtt=0Zab

Хорошая вещь об этом - то, что должно быть совершенно ясно, как распространить это на произвольные полномочия.

Джеффри Шаллит
источник
2
Действительно, очень аккуратно!
Домоторп
1
Ах, гораздо приятнее :-)
Михаэль Кадилхак,
4

Просто другая («ориентированная на грамматику») перспектива, чтобы доказать, что дополнением является CF для любого фиксированного использующего свойства замыкания.{wk}k

Прежде всего обратите внимание, что в дополнении всегда есть такое что . Мы сосредоточимся на и начнем с простой грамматики CF, которая генерирует:{wk}iwiwi+1w1w2

L={a00...0w1b00...0w2...000...0wk|wi|=n}={a0n1b0n(k1)1}

Например, для имеем ,k=3L={ab0,a0b000,a00b00000,...}GL={Sab0|aX00,X0X00|0b0}

Затем примените замыкание при обратном гомоморфизме и объединение :

Первый гомоморфизм:φ(1)a,φ(0)б,φ(1)0,φ(0)0

Второй гомоморфизм:φ(0)a,φ(1)b,φ(1)0,φ(0)0

L=φ1(L)φ1(L) по-прежнему не зависит от контекста

Примените замыкание при циклических сдвигах к чтобы получить множество строк длины не имеющих форму :Lknwk

L=Shift(L)={uuwk|u|=kn} .

Наконец, добавьте обычный набор строк, длина которых не делится на , чтобы получить точное дополнение к :k{wk}

L{{0,1}nnmodk0}={uuwk}

Марцио де Биаси
источник