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: