¿Es el lenguaje de pares de palabras de igual longitud cuya distancia de hamming es 2 o mayor libre de contexto?

¿El siguiente contexto de lenguaje es gratuito?

L = {u x v y ∣ u, v, x, y \in {0, 1}^{+}, | u | = | v |, u \neq v, | x | = | y |, x \neq y}

$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\}$

Como señaló sdcvvc, una palabra en este lenguaje también se puede describir como la concatenación de dos palabras de la misma longitud cuya distancia de hamming es 2 o mayor.

Creo que no está libre de contexto, pero me cuesta probarlo. Traté de intersectar este idioma con un lenguaje normal (como por ejemplo), luego uso el lema de bombeo y \ u homomorfismos, pero siempre obtengo un lenguaje que es demasiado complicado para caracterizar y escribir abajo. $\ 0^*1^*0^*1^*$

formal-languages context-free pushdown-automata pumping-lemma open-problem Robert777
fuente

¿Intentaste bombear la cadena ?

0^{u} 1^{x} 1^{u} 0^{x}

$0^u1^x1^u0^x$

Pål GD

Sí, pero no pude sacar esta cadena del idioma (no significa que no sea posible, solo que no pude hacerlo).

Robert777

@ PålGD, probablemente necesite una forma de "marcar" las piezas, como

1^{u} 0 1^{x} 0 1^{u} 0 1^{x} 0

$1^u 0 1^x 0 1^u 0 1^x 0$

vonbrand

Este lenguaje se puede escribir como donde es la distancia de Hamming. Tenga en cuenta que si reemplazamos 2 por 1, no tiene contexto ( cs.stackexchange.com/questions/307 ) pero el truco utilizado allí no funcionará. Personalmente apuesto a que no es un contexto libre.

{u v : | u | = | v |, d (u, v) \geq 2}

$\{uv:|u|=|v|,d(u,v) \geq 2\}$

d

$d$

sdcvvc

@sdcvvc: Tienes razón, una divide la en para que uno de los bits diferentes esté en y el otro en . Estoy corregido.

u

$u$

u^{'} x

$u'x$

u^{'}

$u'$

x

$x$

András Salamon

Respuestas:

Nota [2019-07-30] La prueba es incorrecta ... la pregunta es más complicada de lo que parece.

Después de un intento fallido aquí es otra idea.

Si intersectamos con el lenguaje regular obtenemos un lenguaje CF. $L$ $L_{reg} = 0^*10^*10^*10^*$

Quizás podamos tener más suerte si usamos (una cadena con exactamente 4 1s). $L_{reg}' = 0^*10^*10^*10^*10^*$

Deje , informalmente si se puede dividir en dos mitades, de modo que la mitad contenga exactamente o ambas mitades contengan dos s pero sus posiciones no coinciden. $L_1 = L \cap L_{reg}'$ $w \in L_1$ $\{0,1,3,4\}$ $1s$ $1$

Suponga que es CF y deje que sea su gramática en forma normal de Chomsky, y deje que $L_1$ $G$

w = u v = 0^{a} 1 0^{b} 1 0^{c} 1 0^{d} 1 0^{e} \in L_{1}

$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L_1$

Tenemos(longitud par) $|u|=|v|$ $d(u,v) \geq 2$

Si restringimos nuestra atención a las formas en que se pueden generar los cuatro 1s de , tenemos los tres casos que se muestran en la parte superior de la figura 1. La parte central de la figura 1 muestra el primer caso (pero los otros son similares) . $w$

ingrese la descripción de la imagen aquí
Figura 1 (la imagen completa se puede descargar aquí )

Si seleccionamos y vemos que los ceros entre los dos pares de 1s deben ser bombeables independientemente (nodos rojos en la figura): en particular, para suficientemente grande , obtenemos un nodo no terminal duplicado en un subárbol interno (nodo X en la figura 2) o una subsecuencia repetida en el camino hacia el primero o el segundo 1 (nodo Y en la figura 2). Tenga en cuenta que la Figura 2 está un poco simplificada: puede haber más nodos no terminales entre las dos s, y también entre las dos ( pero con que produce solo 0s a la derecha del primer 1). $a=e, c=2a$ $b,d \gg a$ $b \gg a$ $X$ $Ys$ $Y\to ... \to Z_i \to ... Y$ $Z_i$

ingrese la descripción de la imagen aquí
Figura 2

Entonces podemos arreglar un arbitrario , luego elegir lo suficientemente grande para obtener un nodo bombeable independientemente en la secuencia de ceros entre el primer y el segundo . Para la secuencia de ceros entre el tercero y el cuarto 1, podemos elegir . Pero es independientemente bombeable, por lo que hay una subcadena bombeable , es decir, tal que y . La cadena que obtenemos es: $a = e = k, c = 2a$ $b$ $1$ $d = b! +b$
$0^b$ $p \leq b$ $y$ $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ $xy^iz = b!+b$

w^{'} = 0^{k} 1 0^{b! + b} 1 0^{2 k} 1 0^{b! + b} 1 0^{k}

$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$

pero . Por tanto, no es CF y finalmente no es CF. $w' \notin L_1$ $L_1$ $L$

Si la prueba es correcta (???) se puede extender a todos los idiomas $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 2$

Vor
fuente

Me temo que la recompensa expirará antes de que podamos verificar esta prueba, por lo que, a menos que surja información drástica en las próximas 4 horas, obtendrá los puntos por ser el mejor intento hasta ahora.

jmite

@jmite: no te preocupes, hay muchas posibilidades de que sea un intento incorrecto como el anterior (que duró aproximadamente 30 minutos antes de descubrir un error trivial) :-) :-)

Vor

¿Por qué la distinción de caso? Las ramas en la gramática no tienen relación con las mitades de la palabra. Pero creo que no importa; Si la prueba funciona, esta distinción de caso no es necesaria. Mirar una gramática supuesta y usar la prueba del lema de Pumping en lugar del lema en sí es un buen truco (uno debería hacer esto con más frecuencia). Tengo una preocupación (real): si bombea una subcadena de , obtendrá ; ¡No veo cómo llegas a. No piense que eso debería dañar la prueba, pero mejor verifique. Además, es posible que desee enderezar alguna notación (y errores tipográficos).

0^{b}

$0^b$

0^{b + p (i - 1)}

$0^{b+p(i-1)}$

b + b!

$b+b!$

Raphael

@Raphael: gracias por los comentarios. Tal vez me equivoque, pero si eliges como longitud objetivoentonces, para cada longitud de bombeo , la cadena se puede descomponer en y se puede bombear a, de hecho, en su ejemplo p seguramente divide, entonces hay un para el cual, pero la longitud de la cadena original es , por lo que la longitud total bombeada es. Lo recuerdo de un par de ejercicios que usan el lema de Ogden ... ahora los revisaré dos veces.

b + b!

$b+b!$

p

$p$

0^{b}

$0^b$

0^{x y z}, (| x y z | = b, | y | = p \leq b)

$0^{xyz}, (|xyz|=b, |y|=p \leq b)$

x y^{i} z = b + b!

$xy^iz = b + b!$

b!

$b!$

(i - 1)

$(i-1)$

p (i - 1) = b!

$p(i-1)=b!$

b

$b$

| x y^{(i - 1)} z | = b + b!

$|xy^{(i-1)}z| = b+b!$

Vor

@Raphael: ... No encontré la prueba en ninguna parte, sino solo un artículo de Zach Tomaszewski que demuestra que el complemento de es CF (ver pregunta ), así que tal vez sea un nuevo resultado (aunque simple); y se puede derivar un teorema de estilo de bombeo-lema para idiomas con cadenas que contienen un número finito de un símbolo particular y subcadenas de longitud arbitraria entre ellas.

L_{d u p} = {w w}

$L_{dup} = \{ ww \}$

Vor

Después de 2 intentos fallidos, que fueron desmentidos por @Hendrik Jan (gracias), aquí hay otro, que no tiene más éxito. @Vor encontró un ejemplo de un lenguaje CF determinista donde se aplicaría la misma construcción, si es correcto. Esto permitió identificar un error en el anclaje de la cadena en la aplicación del lema. El lema en sí no parece tener la culpa. Esta es claramente una construcción demasiado simplista. Ver más detalles en los comentarios. $y$

El lenguaje no está libre de contexto. $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ \}$

Es útil tener en cuenta la caracterización donde d es la distancia de Hamming, propuesta por @sdcvvc. Lo que hay que pensar son 2 posiciones seleccionadas en cada media cadena de manera que los símbolos correspondientes difieran. $L= \{uv:|u|=|v|,d(u,v) \geq 2\}$

Luego considera una cadena tal que e es par. Está claramente en el lenguaje L, cortando y cualquier lugar entre los dos 1. Queremos bombear esa cadena en la primera parte entre los 1, para que se convierta en que se supone que no está en el idioma. $10^i10^j$ $i \lt j$ $i+j$ $u$ $x$ $10^j10^j$

Primero intentamos usar el lema de Ogden , que es como el lema de bombeo, pero se aplica a o más símbolos distinguidos que están marcados en la cadena, siendo la longitud de bombeo de los símbolos marcados (pero el lema puede bombear más porque también puede bombear símbolos sin marcar). El bombeo de longitud marcada depende solo del idioma. Este intento fallará, pero el fracaso será una pista. $p$ $p$ $p$

Entonces podemos elegir y marcamos símbolos en la primera secuencia de 0's. Sabemos que ninguno de los dos 1 estará en la bomba, porque puede bombear una vez (exponente 0) en lugar de bombear. Y bombear los 1 nos sacaría del lenguaje. $i=p$ $i$

Sin embargo, podríamos estar bombeando en ambos lados del segundo 1 tan rápido o incluso más rápido en el lado derecho, para que el segundo 1 nunca llegue al centro de la cadena. Además, el lema de Ogden no fija un límite superior para el tamaño de lo que se bombea, por lo que no es posible organizar el bombeo para obtener el 1 más a la derecha exactamente en el medio de la cadena.

Usamos una versión modificada del lema, aquí llamada Lema de Nash, que puede manejar estas dificultades.

Primero necesitamos una definición (probablemente tenga otro nombre en la literatura, pero no sé cuál, la ayuda es bienvenida). Se dice que una cadena es un borrado de una cadena si se obtiene de borrando símbolos en . Notaremos . $u$ $v$ $v$ $v$ $u \prec v$

Lema de Nash: si es un lenguaje libre de contexto, entonces existen dos números y modo que para cualquier cadena de longitud al menos en , y cada forma de "marcar" o más de las posiciones en , se pueden escribir como con la cadena , , , , , de modo que $L$ $p\gt0$ $q\gt 0$ $w$ $p$ $L$ $p$ $w$ $w$ $w=uxyzv$ $u$ $x$ $y$ $z$ $v$

$xz$ tiene al menos una posición marcada,
$xyz$ tiene como máximo posiciones marcadas, y $p$
hay 3 cadenas , , modo que y z
1. $\hat x \prec x$ , , , $\hat y \prec y$ $\hat z \prec z$
2. $1 \leq \mid \hat x \hat z \mid \leq q$ , , y $1 \leq \mid \hat y \mid \leq q$
3. $ux^j\hat x^i\hat y\hat z^iz^jv$ está en para cada y para cada . $L$ $i \geq 0$ $j \geq 0$

Prueba : Similar a la prueba del lema de Ogden, pero los subárboles correspondientes a las cadenas y se podan para que no contengan ninguna ruta con el doble de no terminales (excepto las raíces de estos dos subárboles). Esto necesariamente limita el tamaño de las cadenas generadas y por una constante . Las cadenas y , para , correspondientes a una versión no podada del árbol, se usan principalmente con para simplificar la contabilidad cuando se aplica el lema. $y$ $xz$ $\hat x\hat z$ $\hat y$ $q$ $x^j$ $z^j$ $j \geq 0$ $j=1$

Modificamos el intento de la prueba anterior, marcando el más a la izquierda símbolos 0, pero son seguidos por símbolos 0 para asegurarse de que bombeamos en la parte izquierda de la cadena, entre los dos 1s. Eso hace un total de 0 entre los 1 (en realidad sería suficiente, ya que el 1 más a la derecha no puede estar en , lo que permitiría simplemente eliminarlo). $p$ $2q$ $i = p + 2q$ $i = p + q$ $\hat z$

Lo que queda es elegir para que podamos bombear exactamente el número correcto de 0 para que las dos secuencias sean iguales. Pero hasta ahora, la única restricción en es ser mayor que . Y también sabemos que el número de 0 que se bombea en cada bombeo está entre 1 y q. Así que sea producto de los primeros enteros. Elegimos . $j$ $j$ $i$ $h$ $q$ $j=i+h$

Por lo tanto, dado que el incremento de bombeo , sea lo que sea, está en , divide . Deje ser el cociente. Si bombeamos exactamente veces, obtenemos una cadena que no está en el idioma. Por lo tanto, L no está libre de contexto. $d$ $[1,q]$ $h$ $k$ $k$ $10^j10^j$

Creo que nunca veré
una cadena encantadora como un árbol.
Porque si no tiene un análisis,
la cadena no es más que una farsa

babou
fuente

Sin embargo, tenga en cuenta que el pase sobre la segunda mitad lee la pila a la inversa. Eso parece significar que las dos posiciones están en la misma posición en ambas mitades, pero a la inversa.

Hendrik Jan

tienes razón ... me hice la tonta ... ahora sé lo que me molestaba en la parte posterior de mi cabeza.

babou

Reconocí el argumento (porque no pude hacerlo funcionar cuando lo intenté yo mismo).

Hendrik Jan

¿Debo dejar esta respuesta incorrecta? Creo que de alguna manera ayuda, ya que hace que el problema sea sospechosamente similar a . El problema es que las reglas del sitio no tienen la intención de alentar resultados incorrectos para la discusión (es decir, no disfruto de los votos negativos más que nadie).

a^{i} b^{j} c^{k} a^{i} b^{j} c^{k}

${a^ib^jc^ka^ib^jc^k}$

babou

@HendrikJan ¿Lo hice otra vez? (Por cierto, gracias por hacer una discusión)

babou

-1

por esta pregunta, creo que tiene contexto y está generado por la siguiente gramática $L$ $\qquad\begin{align} S &\to AXBY \mid BYAX \\ A &\to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1 \\ B &\to 1 \mid 0B0 \mid 0B1 \mid 1B0 \mid 1B1 \\ X &\to 0 \mid 0X0 \mid 0X1 \mid 1X0 \mid 1X1 \\ Y &\to 1 \mid 0Y0 \mid 0Y1 \mid 1Y0 \mid 1Y1 \\ \end{align}$

MK Dadsetani
fuente

Esto es incorrecto; no puede proteger que la longitud de AX sea la misma que BY. Por ejemplo, su gramática genera S -> AXBY -> A011 -> 0A1011 -> 001011 que no está en el idioma original. Además, sus símbolos A y X generan el mismo lenguaje, lo mismo para B e Y; Se pueden fusionar.

sdcvvc