Lema de Pumping

Es importante preguntarse si, dado un lenguaje L, es regular o no.  Desde luego, si L es infinito y regular, se podrá construir un autómata finito o una expresión regular para el mismo.  Entonces, supongamos que un lenguaje es regular y que, por lo tanto, es
aceptado por un AFD M = <E, A, , e0, 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 de 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 de 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: