3.9 LENGUAJES NO REGULARES

El lema de bombeo para lenguajes no regulares

Gracias a este lema podremos demostrar que ciertos lenguajes infinitos no son regulares. Es importante hacer notar que el lema de bombeo es una herramienta adecuada para demostrar que un lenguaje no es regular, pero no lo será para demostrar que un lenguaje si es regular (por el hecho de que existen algunos lenguajes no regulares que la cumplen). Por tanto, si un lenguaje no cumple el lema de bombeo no es regular, pero si lo cumple no podremos decir si es o no regular.

Enunciado del Lema de Bombeo

Para todo lenguaje regular infinito L, existe una constante n, dependiente de ese lenguaje, de forma que si w es una cadena de L con ¦w¦ ≥ n, podemos partir w en tres cadenas, x, y, z, de forma que:

• w = xyz,

• y ≠ ε (o dicho de otro modo, que ¦y¦ ≥ 1),

• ¦xy¦<= n

• Para cualquier k ≥ 0, la cadena xy^kz pertenece a L.

Más formalmente:

∀ lenguaje regular infinito L sobre un alfabeto Σ

∃ n ∈ N /

∀ w ∈ L / ¦w¦ ≥ n

∃ x, y ,z ∈ Σ* / w = xyz, y ≠ ε, ¦xy¦<= n,

∀ k ≥ 0, xy^kz ∈ L

Demostración de que un lenguaje no es regular

Dado que para todo lenguaje regular infinito se cumple el lema de bombeo, si nos dan un lenguaje infinito y demostramos que para él no se cumple, habremos demostrado que no es un lenguaje regular. Como el lema de bombeo es una propiedad que se cumple para todas las cadenas de longitud mayor o igual a cierta n, bastará encontrar una cadena de ese lenguaje, de longitud mayor o igual a esa n, que no se pueda “bombear” para demostrar que el lenguaje no es regular. Con esta idea en mente, los pasos a dar para demostrar que un lenguaje dado no es regular son los siguientes:

1. Elegir una palabra w que pertenezca al lenguaje dado. Podemos elegir cualquier palabra del lenguaje, pero debe ser una cuya longitud sea mayor o igual que una constante n que desconocemos (la constante del lema de bombeo). Como desconocemos n, lo habitual será elegir una palabra en función de un n cualquiera y cuya longitud sea mayor o igual que n.

2. El lema de bombeo dice que si el lenguaje fuera regular, podríamos encontrar una forma de partir esa palabra w en tres, cumpliendo ciertas restricciones, y que esa partición sería bombeable. Como queremos demostrar que el lenguaje no es regular, tendremos que demostrar que no hay ninguna forma de partir la palabra en tres cumpliendo las restricciones del lema, y que después se pueda bombear siempre.

3. Finalmente bastará con encontrar una constante k ≥ 0 que haga que ninguna de las particiones posibles de w sea bombeable.

Más formalmente, para demostrar que un lenguaje L sobre un alfabeto Σ no es regular habrá que demostrar que:

∀ n ∈ N

∃ w ∈ L / ¦w¦ ≥ n,

∀ x, y ,z ∈ Σ* / w = xyz, y ≠ ε, ¦xy¦<= n,

∃ k ≥ 0 / xy^kz ∉ L

Ejemplo de demostración de que un lenguaje no es regular

Sea el lenguaje L={a²ⁿbⁿn≥0}. Demostrando que L no es regular

1. Comprobamos si L es regular por medio del lema de bombeo.

Suponemos que L es regular. Entonces existe una constante n tal que ∀ w ∈ L, ¦w¦ ≥ n,

w = xyz, y ≠ ε, ¦xy¦ <= n, teniendo que xyⁱz ∈ L.

Se elige w = a²ⁿbⁿ, w ∈ L y ¦w¦= 3n y por tanto ¦w¦≥ n.

2. Probamos, por ejemplo, con la siguiente descomposición

w=xyz

- x = a

- y = a

- z = a²^n-2bⁿ

3. Bombeamos:

xy²z = a a a a^2n-2bⁿ = a²ⁿ⁺¹bⁿ

Podemos observar que xy²z no pertenece a L. Por lo tanto, el lenguaje es no regular.

INTEGRANTES:


*TORRES HERNANDEZ JONATHAN DE JESUS
*REYES SANTIAGO SEVERIANO
*RAMIREZ GARCIA PABLO ALBERTO

Nota:

Información recopilada de la siguiente liga:

http://www.alumnos.inf.utfsm.cl/~dcontard/ili-255/documents/ull/uz_cps_lema_bombeo_regulares.pdf