Aaaa

PUMPING LEMMA O LEMA DE BOMBEO PARA LENGUAJES REGULARES.

Si L es un lenguaje finito, es regular y se podrá construir un autómata finito o una expresiónregular para ellos de forma sencilla. También, si L es especificado ya sea por medio de un autómata finito o 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 oun autómata finito puede resultar inútil. En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y queno estén presentes en los lenguajes regulares.

Supongamos que un lenguaje es regular y que, por tanto, es aceptado por un DFA M=(Q, S , q0, d , F), dondeQ 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 de lascadenas de longitud n+1 que pertenecen a L(M).

Si tuviéramos
q1= d (q0, a1)
q2= d (q1, a2)

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

Puesto que j0, y= tk+1 ... tk+j, el loop estk+1 ... tk+j 
  
 
Si la longitud de alguna de las expresiones que forman el lenguaje es mayor que estados, entonces el Lenguaje es 
infinito |L| = 