Una técnica de lenguajes formales que da condiciones necesarias para que un lenguaje sea regular mostrando que cadenas suficientemente largas se pueden descomponer de manera que un subcadena central pueda repetirse (bombear) cualquier número de veces y las cadenas resultantes sigan perteneciendo al lenguaje.

Principio

Un lenguaje regular es reconocido por un autómata finito; cualquier cómputo de aceptación en una entrada suficientemente larga debe visitar algún estado dos veces, produciendo un bucle cuya repetición genera infinitas cadenas relacionadas. Ese bucle implica una descomposición que permite bombear un bloque central.

Demostración

Para demostrar que el lenguaje {a^n b^n : n ≥ 0} no es regular, se asume lo contrario y se aplica el lema de bombeo con su longitud de bombeo; cualquier descomposición exigida por el lema conduce a cadenas bombeadas con números desajustados de a y b, contradiciendo la pertenencia y probando la no regularidad.

Aplicación incorrecta

Usar el lema de bombeo como condición suficiente para regularidad (es solo necesaria), o elegir indebidamente una descomposición sin cuantificar sobre todas las descomposiciones exigidas por el lema, son errores comunes que invalidan pruebas.

Consecuencia

Proporciona un método práctico para probar la no regularidad de lenguajes y razonar sobre las limitaciones de los autómatas finitos; da intuición de por qué la memoria finita impide llevar la cuenta de dependencias no acotadas.

Inversión

La inversa es falsa: un lenguaje que satisface la condición de bombeo para una longitud o descomposición particular puede seguir siendo no regular; se necesitan herramientas más finas (por ejemplo, Myhill–Nerode u Ogden) para distinciones más precisas.

Límite

Se aplica solo a lenguajes regulares y, mediante propiedades de cierre, a ciertos complementos; los lenguajes libres de contexto requieren una versión distinta del lema de bombeo, y el lema no proporciona un autómata constructivo cuando las condiciones fallan.

Tensión semántica

Hay tensión entre el lema de bombeo y otras caracterizaciones de regularidad: Myhill–Nerode ofrece un criterio necesario y suficiente basado en una relación de equivalencia, mientras que el bombeo es solo una propiedad estructural necesaria y puede ser inconcluyente en casos límites.

Síntesis

El lema de bombeo formaliza la limitación de memoria finita de los autómatas finitos: cualquier palabra suficientemente larga aceptada contiene un segmento cíclico repetible que puede bombearse para generar infinitas palabras aceptadas, y la violación de esta propiedad prueba la no regularidad.