Aclaración del lema de bombeo de Sipser

Question

En un libro de Teoría de la Computación que estoy usando, la explicación del Lemma de Bombeo no está mal, pero algunas partes no me quedan claras.

Esta es la definición del lema de bombeo:

Si A es un lenguaje regular, entonces existe un número p (la longitud de bombeo) en el que, si s es cualquier cadena en A de longitud al menos p, entonces s puede dividirse en tres trozos, s = xyz, satisfaciendo las siguientes condiciones:

1. para cada $i \ge 0$ , $xy^iz\in A$ ,
2. $|y| > 0$
3. $|xy|\le p$

Ahora bien, mientras se explica por qué el lenguaje clásico $B=\{0^n1^n\mid n \ge 0\}$ , no es regular, Sipser da las siguientes explicaciones:

Asumir que lo contrario es regular, asumir $B$ es regular. Sea $p$ sea la longitud de bombeo dada por el lema de bombeo. Elija $s$ para que sea la cadena $0^p1^p$ . Porque $s\in B$ y $s$ tiene una longitud superior a $p$ el lema de bombeo garantiza que $s$ puede dividirse en tres partes, $s=xyz$ donde para cualquier $i\ge 0$ la cadena $xy^iz\in B$ .

Sin embargo, estos casos lo hacen imposible (provocando una contradicción):

Caso 1 . La cadena $y$ consiste únicamente en $0$ s. En este caso la cadena $xyyz$ tiene más $0$ s que $1$ por lo que no es un miembro de $B$ violando la condición 1 del lema de bombeo.

Pregunta: No entiendo por qué asumir $y$ se compone únicamente de $0$ s, significa automáticamente que el tring $xyyz$ puede tener más $0$ s que $1$ s. La cadena $x$ puede estar compuesto por cualquier número de $0$ s y la cadena $y$ puede estar compuesto por cualquier número de $1$ s? Mi pregunta es, ¿cómo es que la cadena $xyyz$ resulta en que hay más $0$ s que $1$ s?

Caso 2. La cadena $y$ se compone de $0$ s y $1$ s. En este caso la cadena $xyyz$ pueden tener el mismo número de $0$ s y $1$ s, pero estarán fuera de orden con algunos $1$ s antes de $0$ s. Por lo tanto, no es un miembro de $B$ .

Pregunta: De nuevo, con esta explicación, no entiendo cómo llegaron a la conclusión de que la cuerda $xyyz$ puede tener ambos $0$ s y $1$ pero fuera de orden, provocando una contradicción.

Agradezco cualquier aclaración.

Muchas gracias de antemano.

Answer 1

Parece que hay algo que falla (o es superfluo) en el tratamiento de Sipser (lo que me sorprende). En realidad, el segundo caso nunca es necesario. Intentaré demostrar un ejemplo que se puede llevar fácilmente al caso general.

¡¡¡ADVERTENCIA!!! Lo que sigue es sólo un caso muy especial para demostrar que el lenguaje $L = \{ \mathtt{0}^n \mathtt{1}^n : n \geq 0 \}$ no es regular. Ese caso especial es pensar que la longitud de bombeo de la lengua es $5$ . Para demostrar que $L$ no es regular habría que alterar la secuela para que funcione para cualquier número natural arbitrario $p$ .

Supongamos que $p = 5$ y considerar la cadena $$w = \mathtt{0}^p \mathtt{1}^p = \mathtt{0}^5 \mathtt{1}^5 = \mathtt{0000011111}.$$ Queremos escribir $w = x y z$ de manera que se cumplan las siguientes condiciones:

1. $| x y | \leq p = 5$ ;
2. $| y | > 0$

Dado que la cadena $xy$ debe constituir una parte inicial de $w$ y no puede ser más largo que $5$ caracteres, debe provenir del primer $5$ caracteres de $w$ : estos son $\mathtt{0 0 0 0 0}$ . En particular $y$ debe consistir únicamente en $\mathtt{0}$ s. Además, como $y$ no puede ser la cadena vacía, sino que debe consistir en al menos una $\mathtt{0}$ .

Una posible división de esta cadena es $$\overbrace{\mathtt{00}}^{x}\; \overbrace{\mathtt{00}}^y \; \overbrace{\mathtt{011111}}^{z}.$$

Ahora, cuando "bombeamos" el $y$ obtenemos cadenas como

• $xy^0z = \mathtt{00} \; \mathtt{011111}$ ;
• $xy^1z = \mathtt{00} \; \mathtt{00} \; \mathtt{011111}$ ;
• $xy^2z = \mathtt{00} \; \mathtt{00} \; \mathtt{00} \; \mathtt{011111}$ ;
• etc.

En general, el número de $\mathtt{0}$ s en $x y^i z$ será $5 + (i-1) |y|$ mientras que el número de $\mathtt{1}$ s se mantiene constante en $5$ .

Answer 2

Para su primera pregunta, suponga que $y$ se compone enteramente de ceros. Como $s=0^p1^p$ Esto significa que $x=0^k$ y $y=0^\ell$ para algunos $k\ge 0$ y $\ell\ge 1$ con $k+\ell\le p$ y $z=0^{p-k-\ell}1^p$ es el resto de $s$ . Pero entonces

$$xy^2z=\underbrace{0^k}_x\underbrace{0^{2\ell}}_{y^2}\underbrace{0^{p-k-\ell}1^p}_z$$

tiene $k+2\ell+p-k-\ell=p+\ell>p$ ceros y sólo $p$ los (Recuerde que $\ell>0$ .)

Supongamos ahora que $y$ contiene tanto ceros como unos. Entonces $y=0^k1^\ell$ para algunos enteros positivos $k$ y $\ell$ tal que $k,\ell\le p$ . Esto significa que $x=0^{p-k}$ ya que debe tener el resto de los ceros, y $z=1^{p-\ell}$ . Así,

$$xy^2z=\underbrace{0^{p-k}}_x\underbrace{0^k1^\ell0^k1^\ell}_{y^2}\underbrace{1^{p-\ell}}_z=0^p1^\ell0^k1^p\;.$$

Ahora $p-k$ puede ser $0$ es decir, $x$ puede ser la cadena vacía, pero la cadena $xy^2z$ en su conjunto tiene definitivamente $k>0$ ceros que están a la a la derecha de al menos un $1$ (ya que $\ell\ge 1$ ), lo cual es imposible para cualquier cadena en $B$ .