Es {ww '| HamDist (w, w ')> 1} ¿sin contexto?

Después de leer el reciente pregunta "¿Es el complemento de $\{ www \mid ...\}$ Libre de contexto?" ; Recordé un problema similar que no pude refutar:

Es $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|=|w'| \land HamDist(w,w')>1 \}$ sin contexto?

Aquí requerimos que las dos cadenas difieran en al menos dos posiciones (la distancia de Hamming debe ser mayor que $1$ ).

No tiene contexto si requerimos que $HamDist(w,w')\geq 1$ (es decir, las dos cadenas simplemente deben ser diferentes).

Sospecho que el lenguaje no está libre de contexto: si lo intersectamos con el $0^*10^*10^*10^*$ normal , obtenemos casos en los que un PDA debería "recordar" dos posiciones en orden inverso después de llegar a la mitad de la cadena.

Actualización: si intersectamos $L$ con el $R = \{ 0^*10^*10^*10^* \}$ regular , obtenemos un lenguaje sin contexto como lo muestra domotorp en su respuesta; un $L \cap R'$ un poco más complejo con $R' = \{ 0^*10^*10^*10^*10^*10^* \}$ (un $1$ más para "hacer un seguimiento" de) todavía sugiere que $L$ no debería estar libre de contexto.

fl.formal-languages context-free Marzio De Biasi
fuente

es realmente más fácil, ya que son exactamente las palabras que no tienen la forma

(intersectadas por

L \cap R^{'}

$L\cap R'$

w w

$ww$

R^{'}

$R'$

domotorp

@domotorp: correcto! cambiado a

s fijo impar (a menos que su respuesta se pueda adaptar también a

, para cualquier

impar impar )

1

$1$

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

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

k

$k$

Marzio De Biasi

Un comentario final: no ayuda comenzar con ceros a la izquierda, ya que los lenguajes libres de contexto están cerrados para todo tipo de cambios cíclicos. Podrías simplemente empujarlos a la pila, marcar el último con un símbolo especial, hacer el resto del algoritmo fingiendo que la pila comienza allí, y al final vaciarlo. (Esto usa las transiciones

, pero también es fácil que tales PDA sean equivalentes a las que no tienen)

ϵ

$\epsilon$

Domotorp

podría ser más simple pensar en el alfabeto {0,1,2} y considerar cadenas con exactamente dos 1s y dos 2s. No está en su idioma si la distancia entre 1s y la distancia entre 2s son ambas n.

Kaveh

Respuestas:

La intersección con $R=\{0^*10^*10^*10^*\mid$ palabras de longitud uniforme $\}$ tiene contexto, porque un PDA puede recordar dos posiciones, de una manera. De todos modos, vamos a ver primero lo que este lenguaje $L$ es. Su complemento es $R\setminus L=\{0^a10^b10^c10^d\mid b=n/2 \vee c=n/2 \vee a+d=n/2\}$ . Por lo tanto, $L=\{0^a10^b10^c10^d\mid b\ne n/2 \wedge c\ne n/2 \wedge a+d\ne n/2\}$ . Podemos reescribir esto como $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\}$ .

Los primeros $3$ casos se pueden verificar fácilmente, y también el cuarto.

$b>n/2$ : Comience a colocar en la pila hasta el primer 1, luego comience a aparecer desde la pila hasta que no esté vacío. Después de que esté vacío, nuevamente comience a colocar en la pila hasta llegar al segundo 1. A partir de ese momento, haga estallar la pila.

$c>n/2$ : igual.

$a+d>n/2$ : Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach the third 1. From then on pop the stack.

$b,c,a+d<n/2$ : Start putting in the stack until the first 1, then start popping from the stack until it's non-empty. After it's empty, again start putting in the stack until we reach $a+n/2$ (guessed non-deterministically, somewhere between second and third 1). From then on pop the stack.

domotorp
fuente

Thanks domotorp, I'm reading your idea; I think

R ∖ L

$R \setminus L$ is

{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) \}$ (two 1s on the left half) union its reverse (two 1s on the right half). So how do you get

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

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

Marzio De Biasi

R \subset L

$R\subset L$ is that the HamDist is at most

1

$1$ . This happens exactly if two of the three 1's match, i.e., one is in the same position in the first half, as the other is in the second half. If these two 1's are the first and second 1's, then we get

b = n / 2

$b=n/2$ , if they are the second and third 1's, we get

c = n / 2

$c=n/2$ , and if they are the first and third 1's, we get

b + c = n / 2

$b+c=n/2$ , or equivalently,

a + d = n / 2

$a+d=n/2$ (where I'm cheating a bit with some constant

\pm 1

$\pm 1$ 's).

domotorp

Does this answer the full question?

Michaël Cadilhac

@domotorp: ok I got it, thanks! Another doubt: from

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

$L \cap R = \{...b \neq n/2 \land c \neq n/2...\}$ (which is ok) you write

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 \}$ but, is it equivalent to:

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$ condition omitted)

Marzio De Biasi

@Michael: No.

$~$

domotorp