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

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

Является ли $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \}$ контекста?

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

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

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

Обновление: если мы пересекаем с обычным мы получаем язык без контекста, как показал domotorp в своем ответе; чуть более сложный с (еще один "держать трек" из) до сих пор предполагают , что не должно быть контекстно-свободным. $L$ $R = \{ 0^*10^*10^*10^* \}$ $L \cap R'$ $R' = \{ 0^*10^*10^*10^*10^*10^* \}$ $1$ $L$

fl.formal-languages context-free Марцио де Биаси
источник

на самом деле проще, так как это именно слова, которые не имеют форму

(пересекается с

L \cap R^{'}

$L\cap R'$

w w

$ww$

R^{'}

$R'$

domotorp

@domotorp: правильно! изменено на нечетное фиксированное

с (если ваш ответ не может быть адаптирован также к

, для любого фиксированного нечетного

)

1

$1$

{(0^{*} 1 0^{*})^{k}}

$\{ (0^* 1 0^*)^k \}$

k

$k$

Марцио Де

Последний комментарий: начинать с нуля не следует, поскольку языки без контекста закрыты для всех видов циклических сдвигов. Вы можете просто поместить их в стек, пометить последний специальным символом, выполнить оставшуюся часть алгоритма, делая вид, что стек начинается там, и в конце очищать его. (При этом используются

переходы, но также легко, что такие КПК эквивалентны тем, у которых нет.)

ϵ

$\epsilon$

domotorp

может быть проще подумать об алфавите {0,1,2} и рассмотреть строки с ровно двумя единицами и двумя двумя. Это не на вашем языке, если расстояние между 1 и 2 между равно n.

Каве

Ответы:

Пересечение с $R=\{0^*10^*10^*10^*\mid$ слов четной длины $\}$ зависит от контекста, потому что КПК может запомнить две позиции. Во всяком случае, давайте сначала посмотрим , что этот язык $L$ является. Его дополнение: $R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$ . Следовательно, $L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge c\ne n/2 \wedge a+d\ne n/2\}$ . Мы можем переписать это как $L=\{0^a10^b10^c10^d\mid b> n/2 \vee c> n/2 \vee a+d> n/2 \vee b,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, я читаю вашу идею; Я думаю, что

равен

R ∖ L

$R \setminus L$

{0^{a} 1 0^{b} 1 0^{c^{'}} 0^{c^{″}} 1 0^{d} ∣ (n / 2 = a + b + c^{'} = c^{″} + d + 1) \land [(a = c^{″}) \lor (c^{'} = d)}

$\{ 0^a 1 0^b 1 0^{c'} 0^{c''} 1 0^d \mid \ (n/2=a+b+c'=c''+d+1) \land [(a= c'')\lor (c' = d) \}$ (две 1 в левой половине) объединить его обратное (две 1 в правой половине). Итак, как вы получаете

b = n / 2 \lor c = n / 2 \lor a + d = n / 2

$b=n/2 \vee c=n/2 \vee a+d=n/2$

Марцио Де

в том, что HamDist не больше

. Это происходит точно, если два из трех 1 совпадают, то есть один находится в той же позиции в первой половине, что и другой во второй половине. Если эти два 1 являются первым и вторым 1, то мы получаем

, если они являются вторым и третьим 1, мы получаем

, и если они являются первым и третьим 1, мы получаем

или, что то же самое,

R \subset L

$R\subset L$

1

$1$

b = n / 2

$b=n/2$

c = n / 2

$c=n/2$

b + c = n / 2

$b+c=n/2$

a + d = n / 2

$a+d=n/2$ (где я немного изменяю с некоторой константой

\pm 1

$\pm 1$

domotorp

Это отвечает на полный вопрос?

Михаэль Кадилхак

@domotorp: хорошо, я понял, спасибо! Еще одно сомнение: из

(это нормально) вы пишете

, но, это эквивалентно:

L \cap R = {. . . b \neq n / 2 \land c \neq n / 2...}

$L \cap R = \{...b \neq n/2 \land c \neq n/2...\}$

L \cap R = {. . . b > n / 2 \lor c > n / 2 \lor b, c < n / 2}

$L \cap R = \{ ...b > n/2 \lor c > n/2 \lor b,c < n/2 \}$

? (условие

опущено)

L \cap R = {. . . (b < n / 2 \lor b > n / 2) \land (c < n / 2 \lor c > n / 2)}

$L \cap R = \{... (b < n/2 \lor b >n/2) \land (c < n/2 \lor c >n/2)\}$

a + d

$a+d$

Марцио Де

@ Майкл: Нет.

$~$

Domotorp