Lema de bombeo: probar que algo no se puede

Probar que algo se puede es fácil: se muestra la máquina. Probar que no se puede es otra cosa, porque hay infinitos autómatas posibles y no alcanza con fracasar unas cuantas veces. El lema de bombeo es la herramienta que convierte esa imposibilidad en una contradicción concreta.

La intuición es el principio del palomar

La intuición sale del principio del palomar. Un autómata tiene una cantidad finita de estados, digamos $p$. Si procesa una cadena más larga que $p$, forzosamente repite un estado.

Entre las dos visitas al mismo estado hay un tramo que forma un ciclo. Y si hay un ciclo, se puede recorrer cero veces, una, o mil: el autómata no distingue. Todas esas cadenas terminan en el mismo estado final y, por lo tanto, todas se aceptan o todas se rechazan.

El enunciado y sus tres condiciones

Formalmente: si $L$ es regular, existe un $p$ tal que toda cadena $w \in L$ con $|w| \ge p$ se puede partir en $w = xyz$ cumpliendo tres condiciones: $|y| > 0$, $|xy| \le p$, y $xy^{i}z \in L$ para todo $i \ge 0$.

Las dos primeras condiciones son las que dan fuerza a la demostración. $|y|>0$ dice que el tramo bombeable no es vacío; $|xy| \le p$ dice que está cerca del principio, y eso permite controlar qué símbolos contiene.

Usarlo es jugar un juego con turnos fijos

Se usa por contradicción, y conviene pensarlo como un juego con turnos fijos. El adversario elige $p$. Uno elige la cadena $w$, en función de $p$. El adversario elige la partición. Uno elige el $i$ que rompe todo.

El error más común es elegir la partición uno mismo: hay que refutar todas las particiones posibles. Por eso la elección de $w$ es lo único que realmente se decide, y hay que elegirla de modo que la condición $|xy| \le p$ deje al adversario sin opciones útiles.

El caso clásico, paso por paso

El caso clásico: $L = \{a^n b^n\}$. Se elige $w = a^p b^p$. Como $|xy| \le p$, el tramo $y$ está formado únicamente por aes, cualquiera sea la partición.

Bombear con $i=2$ agrega aes sin agregar bes, y la cadena resultante tiene más aes que bes: no está en $L$. Contradicción, así que $L$ no es regular. Toda la demostración cabe en un párrafo, y la clave fue elegir una cadena donde el prefijo de largo $p$ fuera homogéneo.

Dos cuidados que invalidan media demostración

Hay dos cuidados importantes. El lema es una condición necesaria, no suficiente: un lenguaje puede cumplir la propiedad de bombeo y aun así no ser regular. Sirve para refutar, nunca para confirmar.

Y muchas veces hay un camino más corto. Como los regulares son cerrados bajo intersección y complemento, se puede probar que un lenguaje no es regular intersecándolo con uno que sí lo es y llegando a un lenguaje ya conocido como no regular. El teorema de Myhill-Nerode da otra vía, y a diferencia del lema es una caracterización exacta.

La versión para libres de contexto

Existe la versión para lenguajes libres de contexto, con la misma idea aplicada al árbol de derivación: si el árbol es lo bastante alto, una variable se repite en un camino, y el tramo entre las dos apariciones se puede repetir.

Ahí la cadena se parte en cinco, $w = uvxyz$, y se bombean dos tramos a la vez. Con eso se prueba que $a^n b^n c^n$ no es libre de contexto, que es el resultado que separa ese nivel del siguiente.

Cómo se usa, y qué no prueba

La estructura es un juego contra un adversario, y escribirla así evita el error más común. Para $a^nb^n$, la cadena que funciona es $a^pb^p$: como $|xy| \le p$, el tramo bombeable está enteramente dentro de las aes, y bombearlo desbalancea la cantidad. Elegir en cambio $(ab)^p$ deja particiones que sobreviven, y la demostración no sale.

Lo que preguntan sobre esto

Cierre

El lema de bombeo traduce “la máquina tiene memoria finita” en “toda cadena larga tiene un ciclo repetible”. La demostración es un juego donde lo único que se elige es la cadena, y hay que refutar todas las particiones. Sirve para refutar, no para confirmar.