lenguajes no regulares

20
Instituto Tecnológico de La Piedad

Upload: alfredo-armendariz

Post on 04-Jul-2015

104 views

Category:

Education


1 download

TRANSCRIPT

Page 1: Lenguajes no regulares

Instituto Tecnológico de La Piedad

Page 2: Lenguajes no regulares

Matemáticas Discretas ll

LENGUAJES NO REGULARES

Por: Alfredo Armendáriz

Page 3: 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.

Page 4: Lenguajes no regulares

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 xykz 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, xykz ∈ L

Page 5: Lenguajes no regulares

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:

Page 6: Lenguajes no regulares

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.

Page 7: Lenguajes no regulares

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 / xykz ∉ L

Page 8: Lenguajes no regulares

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

Sea el lenguaje L={a²nbnn≥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 xyiz ∈ L.

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

Page 9: Lenguajes no regulares

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

w=xyz

- x = a

- y = a

- z = a²n-2bn

3. Bombeamos:

xy²z = a a a a2n-2bn = a2n+1bn

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

Page 10: Lenguajes no regulares

Gracias Por su atención

Page 11: Lenguajes no regulares

Bibliografía http://teodelacomp.blogspot.mx/2011/03/39-lenguajes-no-

regulares.html 30/01/2014/04:44 p.m.

Page 12: Lenguajes no regulares

Instituto Tecnológico de La Piedad

Page 13: Lenguajes no regulares

Matemáticas Discretas ll

LENGUAJES NO REGULARES

Por: Alfredo Armendáriz

Page 14: Lenguajes no regulares

Introducción

Uno de los conceptos más importantes es

el de lenguaje, pero para poder definirlo

conoceremos otros conceptos anteriores.

Page 15: Lenguajes no regulares

Alfabeto. Es un conjunto no vacío de símbolos. Así, el alfabeto del

idioma es español, E= {a,b,c,...z}, es solo uno de tantos alfabetos.

Palabra. Con los símbolos de un alfabeto es posible formar

secuencias o cadenas de caracteres a estas cadenas se les llama

palabras.

Lenguaje. Es un conjunto de palabras.

Page 16: Lenguajes no regulares

Todos los lenguajes no son regulares, simplemente hay que tener

en cuenta que los lenguajes regulares son definidos por una expresión.

No hay ningún método que nos permita decidir sin un lenguaje es

regular o no, ya que depende de la descripción del lenguaje.

Aun que si que tenemos diferentes herramientas que permiten probar

que lenguajes específicos no son regulares.

Page 17: Lenguajes no regulares

1. Asumir que es un lenguaje aceptado por un autómata.

2. Tomar una palabra suficientemente larga.

3. Dividir en tres partes x;y;z.

4. Demostrar que cualquier división de la palabra y en tres

partes no se puede bombear la parte del medio.

Page 18: Lenguajes no regulares

Conclusión

Lenguaje no regular. Es aquel lenguaje que

no es muy común, es en el cual tomas una

palabra, la divides en 3 partes y no son del

mismo tamaño ósea que no se pueden

comprar las partes.

Page 19: Lenguajes no regulares

Gracias por su

atención

Page 20: Lenguajes no regulares

Bibliografía https://www.youtube.com/watch?v=cyMsczWwzJA