Lema Pumping

Dado un lenguaje L es importante preguntarse si el mismo es regular o no.  Desde luego, si L es finito y regular, se podrá construir un autómata finito o una expresión regular para el mismo.  También, si L es especificado ya sea por medio de un autómata finito o por una expresión regular, la respuesta es obvia.  Por desgracia, hay relativamente pocos lenguajes que sean regulares y, en el caso de un lenguaje infinito, la búsqueda exhaustiva de una expresión regular o un autómata finito puede resultar inútil.  En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y que no estén presentes en los lenguajes no regulares.
Entonces, supongamos que un lenguaje es regular y que, por lo tanto, es aceptado por un AFD M = <E, A, , s, F>, donde E contiene n estados.  Si L(M) es infinito, podremos encontrar cadenas cuya
longitud sea mayor que n.  Supongamos que w = a1,a2 ... an+1 es una cadena de longitud n+1 que pertenece a L(M).
Si se tuviera

y así, sucesivamente, se obtendrían los n+1 estados, q1, q2, ... ,qn+1 .  Puesto E contiene solo n estados, los qi no serán todos distintos.  En consecuencia, para algunos índices j y k, con 1<=j < k <= n+1, se obtendrá que qj = qk.  Por lo tanto, tendremos un ciclo en el camino que parte de s hasta un estado de aceptación.


Puesto que j < k, se tiene que la "parte central",  es decir, aj+1... ak, tiene al menos longitud 1.  Obsérvese además que la cadena w' = a1...akaj+1...an+1  debe pertenecer también a L(M).  Por esto, se puede dar vueltas en el ciclo tantas veces como se quiera, de forma que a1...aj(aj+1... ak)mak+1.. an+1  estará en L(M) para todo m >= 0.

Luego de lo expuesto anteriormente se esta en condiciones de enunciar el Lema Pumping de la siguiente forma:


donde podemos definir las cadena u, v y w de la siguiente forma:

    u  = primeros símbolos de x que permiten alcanzar el estado q.
    v  = los siguientes símbolos de x que permitirán alcanzar de nuevo al estado q.
    w  = resto de la cadena x.
 

Prueba de lenguajes no regulares
Frecuentemente, el lema Pumping es utilizado para probar que ciertos lenguajes no son regulares.  Para llevar a cabo esto se debe probar que el lenguaje no satisface el lema.  Por lo tanto, se puede utilizar el contrarecíproco del lema de la siguiente manera: