Elegir $x$ , $y$ , $z$ partes en un lema de bombeo $w$ cadena

Question

Quiero probar que $L = \left\{u0v \mid u, v \in \{0, 1\}^* \land \#_1(u) = \#_0(v) \right\}$ no es regular. Pero mi comprensión del lema de bombeo de alguna manera no es a prueba de balas, así que no estoy seguro de si estoy en lo correcto en lo que estoy haciendo.

Elegí $w$ ser $1^k00^k = xyz$ Así que $|w| \ge k$ lo cual es correcto, espero. Ahora no estoy muy seguro de cómo elegir correctamente lo que es $x,y$ en esta cadena. Puede $y$ ser cualquier parte de $w$ (teniendo en cuenta la condición $|xy| \le k$ )? Por ejemplo $x$ sea igual a $1^m$ , $y$ entonces será $1^n$ y $z$ será $00^{m+n}$ (donde $m+n = k$ ). Suponiendo entonces que $xy^iz \in L$ para $i\ge0$ , dejemos que $i$ sea $0$ . Entonces sólo hay una cadena $1^m00^{m+n}$ izquierda, que no es de $L$ . ¿Es correcta esta prueba? En cierto modo tiene sentido, pero no puedo decir si todos los pasos que he dado son correctos.

Answer 1

Dentro de cualquier subcadena de longitud $>k$ puede encontrar una subcadena bombeable. Así que tomando esa subcadena dentro del $0$ parte está bien. Usted debe tratar de entender el lema de bombeo, en lugar de simplemente aplicarlo, la idea es simple: si usted va $k+1$ veces a $k$ lugares, tienes que ir al mismo sitio en algún momento (como ir de bar en bar, el autómata está "saltando de lugar").