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: