Is {ww '| HamDist (w, w ')> 1} не зависит от контекста?

13

После прочтения недавнего вопроса «Является дополнение {www...} Контекстно-свободным?» ; Я вспомнил похожую проблему, которую не смог опровергнуть:

Является ли L={www,w{0,1}|w|=|w|HamDist(w,w)>1} контекста?

Здесь мы требуем, чтобы две строки отличались как минимум в двух положениях (расстояние Хэмминга должно быть больше 1 ).

Он не зависит от контекста, если нам требуется (т.е. две строки должны просто отличаться).HamDist(w,w)1

Я подозреваю, что язык не является контекстно-свободным: если мы пересекаем его с обычным мы получаем случаи, когда КПК должен «запоминать» две позиции в обратном порядке после достижения половины строки.0101010

Обновление: если мы пересекаем с обычным мы получаем язык без контекста, как показал domotorp в своем ответе; чуть более сложный с (еще один "держать трек" из) до сих пор предполагают , что не должно быть контекстно-свободным.LR={0101010}LRR={01010101010}1L

Марцио де Биаси
источник
на самом деле проще, так как это именно слова, которые не имеют форму w w (пересекается с R ). LRwwR
domotorp
@domotorp: правильно! изменено на нечетное фиксированное с (если ваш ответ не может быть адаптирован также к { ( 0 1 0 ) k } , для любого фиксированного нечетного k )1{(010)k}k
Марцио Де
Последний комментарий: начинать с нуля не следует, поскольку языки без контекста закрыты для всех видов циклических сдвигов. Вы можете просто поместить их в стек, пометить последний специальным символом, выполнить оставшуюся часть алгоритма, делая вид, что стек начинается там, и в конце очищать его. (При этом используются переходы, но также легко, что такие КПК эквивалентны тем, у которых нет.)ϵ
domotorp
может быть проще подумать об алфавите {0,1,2} и рассмотреть строки с ровно двумя единицами и двумя двумя. Это не на вашем языке, если расстояние между 1 и 2 между равно n.
Каве

Ответы:

4

Пересечение с R={0101010 слов четной длины } зависит от контекста, потому что КПК может запомнить две позиции. Во всяком случае, давайте сначала посмотрим , что этот язык L является. Его дополнение: RL={0a10b10c10db=n/2c=n/2a+d=n/2} . Следовательно, L={0a10b10c10dbn/2cn/2a+dn/2} . Мы можем переписать это как L={0a10b10c10db>n/2c>n/2a+d>n/2b,c,a+d<n/2} .

Первые 3 случая можно легко проверить, как и четвертый.

b>n/2 : начать складывать в стек до первой 1, затем начинать выталкивать из стека, пока он не будет пустым. После того, как он опустеет, снова начните складывать в стек, пока мы не достигнем второго 1. После этого вытолкните стек.

c>n/2 : то же самое.

a+d>n/2 : начать складывать в стек до первой 1, затем начинать выталкивать из стека, пока он не будет пустым. После того, как он опустеет, снова начните складывать в стек, пока мы не достигнем третьего 1. После этого вытолкните стек.

b,c,a+d<n/2 : начните помещать в стек до первой 1, затем начинайте извлекать из стека, пока он не будет пустым. Послеон пуст, снова положить начало в стек до тех порне достигнемa+n/2 (угадали недетерминированно, гдето между вторым и третьим 1). С тех пор поп стек.

domotorp
источник
Спасибо domotorp, я читаю вашу идею; Я думаю, что равен { 0 a 1 0 b 1 0 c 0 c 1 0 d( n / 2 = a + b + c = c + d + 1 ) [ ( a = c ) ( c = d ) }RL{0a10b10c0c10d (n/2=a+b+c=c+d+1)[(a=c)(c=d)}(две 1 в левой половине) объединить его обратное (две 1 в правой половине). Итак, как вы получаете ? b=n/2c=n/2a+d=n/2
Марцио Де
в том, что HamDist не больше 1 . Это происходит точно, если два из трех 1 совпадают, то есть один находится в той же позиции в первой половине, что и другой во второй половине. Если эти два 1 являются первым и вторым 1, то мы получаем b = n / 2 , если они являются вторым и третьим 1, мы получаем c = n / 2 , и если они являются первым и третьим 1, мы получаем b + c = n / 2 или, что то же самое, a + d = n / 2RL1b=n/2c=n/2b+c=n/2a+d=n/2(где я немного изменяю с некоторой константой ). ±1
domotorp
Это отвечает на полный вопрос?
Михаэль Кадилхак
@domotorp: хорошо, я понял, спасибо! Еще одно сомнение: из (это нормально) вы пишете L R = { . , , б > п / 2 с > п / 2 Ь , с < п / 2 } , но, это эквивалентно: L RLR={...bn/2cn/2...}LR={...b>n/2c>n/2b,c<n/2} ? (условие a + d опущено)LR={...(b<n/2b>n/2)(c<n/2c>n/2)}a+d
Марцио Де
@ Майкл: Нет. 
Domotorp