¿Cómo se puede probar que $\{w \mid \text{ w tiene una longitud par y la primera mitad de w tiene más 0s que la segunda mitad de w} \}$ no es regular?

Question

He tenido algunas dificultades para entender las pruebas de que un lenguaje no es regular utilizando el Lema del Bombeo, y ahora necesito demostrar que el siguiente lenguaje

$$A = \{w \mid \text{ w tiene longitud par y la primera mitad de w tiene más 0s que la segunda mitad de w} \}$$

no es regular.

Empezaría asumiendo que $A$ es regular, y luego debería elegir una cadena en $A$ que para cierto $p$ (longitud de bombeo) contradiría las suposiciones, es decir, que $A$ es regular.

Pienso que primero necesito elegir una cadena $s$, que por supuesto debe tener longitud par, y la primera parte de esa cadena debe contener más $0$s que la segunda parte. Por ejemplo, $0001$ sería una cadena en $A$.

La longitud de $s$ debe ser mayor o igual a $p. Además, $s$ puede dividirse en tres partes, como $s = xyz$.

Ahora, ¿cómo elegiría $s$? Vi que algunas pruebas hacen que $s$ dependa de $p$. ¿Es estrictamente necesario esto, o es simplemente conveniente, y por qué?

¿Podrías ayudarme a continuar con la prueba, por favor?

Answer 1

Definir $s$ parcialmente en términos de $p$ es una manera fácil de asegurar que $|s|\ge p$; esto es necesario si queremos aplicar el lema del bombeo. También nos da cierto control sobre cómo se verá la parte $xy$ de la descomposición $xyz.

Aquí comenzaría con un $s$ que apenas cumple con la condición para estar en $A$: $s=0^p10^{p-1}$. Si $A$ fuera regular, habría una descomposición $s=xyz$ de manera que $|xy|\le p$, $|y|\ge 1$, y $xy^kz\in A$ para cada $k\ge 0. Dado que $|xy|\le p$, sabemos que $xy$ es una cadena de ceros: es parte de la subcadena inicial $0^p$ de $s$. Así, hay $i, j$ tal que $x=0^i$, $y=0^j$, $i+j\le p$, $i\ge 0$, y $j\ge 1. (Sabemos que $j\ge 1$, porque $j=|y|\ge 1.) Esto significa que $z=0^{p-(i+j)}10^{p-1}$, y nuestra descomposición es

$$s=x\color{red}y\color{blue}z=0^i\color{red}{0^j}\color{blue}{0^{p-(i+j)}10^{p-1}\;.$$

Ahora, ¿cómo se ve $xy^kz$ para $k\ge 0? Es

$$xy^kz=0^i(0^j)^k0^{p-(i+j)}10^{p-1}=0^{i+kj+p-i-j}10^{p-1}=0^{p+(k-1)j}10^{p-1}\;.$$

En particular, cuando $k=0$, se tiene $xz=0^{p-j}10^{p-1}$, donde $j\ge 1. ¿Puedes ver por qué esta palabra no puede estar en $A$?

Answer 2

Sí, este lenguaje puede ser demostrado como no regular usando el lema del bombeo. La declaración más fuerte del lema del bombeo funcionará: si $L$ es regular, entonces hay un $p$ (igual al número de estados en un DFA que acepta $L$), de tal manera que para cualquier cadena $s\in L$, cualquier subcadena $r$ de $s$ de longitud $\ge p$ tiene subcadenas que pueden ser "bombeadas". La prueba es la misma: dada cualquier subcadena $r$ de $s$ con $\lvert r\rvert\ge p$, los estados que el DFA debe atravesar cuando "procesa" $r$ son $p+1$ en número, así que debe haber repetición.)

Si el $L$ en cuestión fuera regular, dejemos que $p$ sea la longitud dada por el lema del bombeo y consideremos $s=0^{p+1}1^p$. Entonces $s\in L$. Pero alguna subcadena de los $1$s puede ser bombeada, y las cadenas resultantes estarán en $L$. Pero claramente eso no es cierto: las cadenas "infladas" no cumplirán con la definición del lenguaje.