Lema Del Bombeo Para Lenguajes Libres De Contexto

El Lema del Bombeo para Lenguajes Libres de Contexto (LLC) es una herramienta para probar que un lenguaje no es un LLC. Dice que si un lenguaje es un LLC, entonces cualquier cadena "larga" en ese lenguaje tiene una propiedad especial: podemos "bombear" parte de la cadena, repitiéndola, y la nueva cadena resultante seguirá estando en el lenguaje.

¿Qué significa "bombear"?

Imagina que tienes una cadena larga w. El Lema del Bombeo dice que podemos dividir esta cadena en cinco partes: u, v, x, y, z, de tal manera que:

• La cadena original w = uvxyz.
• vy no está vacía (es decir, tiene al menos un símbolo).
• vxy no es muy larga. Su longitud total es menor o igual a una constante p, que depende del lenguaje. (Esta constante p se llama la "longitud de bombeo").
• Para cualquier número i (0, 1, 2, ...), la cadena uvⁱxyⁱz también está en el lenguaje. Aquí, vⁱ significa v repetida i veces (análogamente para yⁱ). Si i=0, significa que simplemente eliminamos v e y.

La idea principal es que podemos repetir o eliminar las partes v e y de la cadena, y el resultado siempre será una cadena válida en el lenguaje.

Ejemplo: El lenguaje L = { aⁿbⁿcⁿ | n >= 0 } no es un LLC

Vamos a usar el Lema del Bombeo para demostrar que el lenguaje L = { aⁿbⁿcⁿ | n >= 0 }, que contiene cadenas como "abc", "aabbcc", "aaabbbccc", etc., no es un Lenguaje Libre de Contexto (LLC).

Supongamos, para llegar a una contradicción, que L sí es un LLC. Entonces, existe una longitud de bombeo p. Consideremos la cadena w = a^pb^pc^p (una cadena con p "a"s, p "b"s, y p "c"s). Esta cadena pertenece a L y tiene longitud mayor que p.

Según el Lema del Bombeo, podemos dividir w en uvxyz cumpliendo las condiciones mencionadas antes. Ahora, analizamos diferentes casos para vy:

1. Si vy contiene sólo "a"s, o sólo "b"s, o sólo "c"s, al bombear (uv²xy²z) tendremos más de esas letras, pero la cantidad de las otras letras se mantiene igual. Por lo tanto, la cadena resultante no estará en L.
2. Si vy contiene "a"s y "b"s, o "b"s y "c"s, al bombear, tendremos las "a", "b" y "c" mezcladas, lo que no está permitido en L.

En todos los casos, encontramos que uvⁱxyⁱz no pertenece a L para algún i. Esto contradice el Lema del Bombeo. Por lo tanto, nuestra suposición inicial (que L es un LLC) es incorrecta. Concluimos que L no es un LLC.

Cómo usar el Lema del Bombeo

El Lema del Bombeo se usa por contradicción. Para probar que un lenguaje no es un LLC:

1. Asume que el lenguaje sí es un LLC.
2. Entonces, existe una longitud de bombeo p.
3. Elige una cadena w en el lenguaje que tenga longitud mayor que p. La elección de w es crucial. Debes elegir una cadena que dificulte el bombeo.
4. Muestra que para todas las posibles divisiones de w en uvxyz que cumplan las condiciones del Lema del Bombeo, existe algún valor de i para el cual uvⁱxyⁱz no está en el lenguaje. Esto usualmente se hace analizando casos.
5. Concluye que tu suposición inicial era incorrecta, y por lo tanto, el lenguaje no es un LLC.