Lema de pumping

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

El lema de pumping permite demostrar cuando un lenguaje no es regular o no es libre de contexto. Si el lema se cumple no necesariamente implica que el lenguaje sea regular o libre de contexto.

Lenguajes regulares[editar]

El lema de pumping expresa que dada una longitud mínima n (que depende del lenguaje), todas las cadenas z de longitud mayor o igual a n pueden escribirse como z = uvw, donde uv no supera a n, v es no vacía y es posible repetir tantas veces v como se desee sin que la cadena deje de pertenecer al lenguaje. Es decir, pertenece al lenguaje.

Intuitivamente, significa que existe una longitud n (para la cual puede tomarse la cantidad de estados del AFD mínimo que captura el lenguaje) tal que toda cadena mayor o igual resulta de haber realizado al menos un ciclo sobre uno de los estados del autómata. Esto es, si se tiene w = xyz, se obtiene un recorrido de la siguiente forma.

Lema de pumping

Notar que la cadena y debe ser no vacía para que el ciclo efectivamente exista, xy es menor que la cantidad de estados del autómata, y la cadena total debe superar la cantidad de estados (o podría ser capturada por el autómata sin efectuar ningún ciclo). Expresado en transiciones de configuraciones instantáneas:

Como y por la propiedad ya demostrada, es posible repetir y tantas veces como se desee y volver siempre al mismo estado, que tras consumir la cadena z se sabe que lleva a un estado final con lo que la cadena resulta aceptada.

El lema de pumping es una manera útil de determinar si un lenguaje es regular o no. Si no verifica este lema, entonces se sabe que no es regular. Notar que la implicación no vale a la inversa, esto es, un lenguaje no regular puede cumplir pumping de regulares. En estos casos generalmente se recurre a demostrar que el complemento, inverso, unión o alguna combinación a partir de dicho lenguaje no lo verifica.

Transición para configuraciones instantáneas[editar]

La función de transición entre dos configuraciones instantáneas se define como sii existe una transición de q a p por a. Asimismo se define la función de transición generalizada.

Vale que si , entonces para cualquier . Es decir, si es posible hacer un loop sobre el estado q consumiendo la cadena alfa, entonces es posible realizar ese loop tantas veces como se desee. Se demuestra fácilmente por inducción en la cantidad de repeticiones de alfa.

Lenguajes independientes de contexto[editar]

El lema de pumping para LIC es similar al de gramaticas regulares. La idea es que para toda cadena que supere una longitud critica n del lenguaje (puede tomarse ), la cadena pueda descomponerse en 5 partes r,x,y,z,s tal que puedan insertarse tantas repeticiones de x y z como se desee y que la cadena se mantenga en el lenguaje. Se pide ademas que la longitud de x+z sea no nula (para que haya algo a insertar) y que x+y+z no supere a n.

La demostracion parte de una cadena y un arbol de derivacion minimo T (es decir, de altura minima). Usando el lema de la altura, puede probarse que , lo que lleva a que .

En otras palabras, si la cadena es lo suficientemente grande, entonces la altura del arbol que la genera sera mayor estricto a la cantidad de simbolos no terminales que tiene la gramatica. Por lo tanto, recorriendo la rama mas larga del arbol, debe haber por lo menos un no terminal repetido (supongamos A).

Se considera entonces que la aparicion mas baja de A genera la cadena y, mientras que la siguiente genera xyz (lease vwx en la figura).

PumpingCFL.PNG

Esto significa que A deriva (en uno o mas pasos) tanto en y como en xyz, y que S deriva en rAs. Haciendo induccion en la cantidad de apariciones de x y z (caso base es cero) es sencillo ver que A termina derivando en xAz o y, con lo que es forma sentencial del lenguaje.