Lema del bombeo en los lenguajes regulares
Nosotros sabemos que un lenguaje regular es aquel al cual le podemos construir un automata finito que lo acepte
bueno, el lema del bombeo es una propiedad que tienen los lenguajes regulares, y que nos sirve para saber si un lenguaje infinito es regular o no.
supongamos lo siguiente...
el automata resultante de esa expresion regular seria algo asi como en la "imagen 1".
como se ve, se puede contruir un automata con estados finitos para este lenguaje regular que tiene infinitas cadenas.
pero si tenemos la siguiente expresion:
aⁿbⁿ (donde n es un numero natural)
esta expresion no se la puede representar con un automata finito y ahora veremos porque.
si quisieramos representar esa expresion en un automata finito, nos daremos cuenta que el numero de estados de nuestro automta crece exponencialmente, debido a que si "n" es igual a 5 por ejemplo, como no es una clausura de kleene que nos dice que puede haber cualquier cantidad de "a" y cualquier cantidad de "b", tendremos que tener si o si 5 estados para cada simbolo "a", y de la misma manera 5 estados para cada simbolo "b" ya que a y b estan elevados al mismo exponente, tendremos que acerlo de esa manera porque el automata no tiene una manera de recordar cuantas veces repetimos "a" anteriormente para hacerlo de igual manera con "b"
Dijimos anteriormente que un lenguaje regular puede ser infinito,, y a ese lenguaje se lo puede representar por un automata finito.
asi que, que pasa si hacemos ese lenguaje aⁿbⁿ en un lenguaje infinito? siendo "n"=0, 1, 2, 3..... hasta el infinito?
en ese caso tendriamos tantos estados que seria imposible construirlo, ya que como dije, el automata no tiene una memoria que le diga cuantas veces se repitio cada simbolo...
Un automata de este tipo, que describe gramaticas de tipo 3, con estados finitos, transiciones, y estados de aceptacion, haceptan si o si cualquier lenguaje regular nada mas, si hay un lenguaje que no puede ser representado por estos, es porque no es regular
Vamos a ver como se puede saber si un lenguaje infinito es regular, de una manera mas formal.
el lema del bombeo dice que, si un lenguaje "L" es regular, entonces existe un numero entero P>=0
y que cualquier cadena w del lenguaje L de longitud mayor o igual a P, puede ser partida en 3 cadenas diferentes, asi: w = xyz.
pero para dividir una cadena en 3 subcadenas, se deben cumplir las siguientes condiciones:
1) las cadenas "xy" juntas, deben formar en total una cadena de longitud menor o igual a "P"
2) la cadena y tiene que ser de longitud mayor o igual a 1
3) siendo "n" cualquier numero natural, si elevamos la cadena "w" de esta manera xyⁿz, obtenemos otra cadena que tambien pertenece al lenguaje
por ejemplo:
tenemos el lenguaje descrito por la siguiente expresion : abⁿa
como ya sabemos, el valor de "n" puede ser cualquiera, este lenguaje es infinito, pero no sabemos si es regular, para eso deberia cumplir las propiedades.
elejimos un valor para P por ejemplo, P = 4
ahora elejimos una cadena de ese lenguaje que contenga igual o mas simbolos que P
ejemplo, la cadena -----> w = abba
esta cadena debemos dividirla en tres subcadenas xyz
siguiendo las condiciones, podemos dividir la palabra w = abba en...
resultaria en una nueva cadena w = abbbba
si ven, la nueva cadena tambien pertenece al lenguaje L = abⁿa, cumple la propiedad de bombeo, entonces es regular.
vamos a hacer de la misma manera con la expresion aⁿbⁿ
elegimos un valor de P. P = 5
una cadena de ese lenguaje con 5 o mas simblos, podria ser w = aaabbb
la dividimos en 3 cadenas siguiendo las condiciones. x=a y=aab z=bb
resolvemos xyⁿz, teniendo en cuenta que "n" vale por ejemplo n=2
la cadean resultante seria w = aaabaabbb
como la cadena no pertenece al lenguaje aⁿbⁿ entonces no es regular.
En otro post explicare con que automatas se puede reconocer estos lenguajes no regulares e infinitos.
bueno, el lema del bombeo es una propiedad que tienen los lenguajes regulares, y que nos sirve para saber si un lenguaje infinito es regular o no.
supongamos lo siguiente...
a*b*
es una expresion regular que forma un lenguaje, compuesto por cualquier cantidad de "a" seguido por cualquier cantidad de "b", incluida la cadena vacia, ya que tenemos la clausura de kleene en los dos simbolos. Es un lenguaje infinito, y se le puede construir un automata finito que lo hacepteel automata resultante de esa expresion regular seria algo asi como en la "imagen 1".
 |
| imagen 1 |
como se ve, se puede contruir un automata con estados finitos para este lenguaje regular que tiene infinitas cadenas.
pero si tenemos la siguiente expresion:
aⁿbⁿ (donde n es un numero natural)
esta expresion no se la puede representar con un automata finito y ahora veremos porque.
si quisieramos representar esa expresion en un automata finito, nos daremos cuenta que el numero de estados de nuestro automta crece exponencialmente, debido a que si "n" es igual a 5 por ejemplo, como no es una clausura de kleene que nos dice que puede haber cualquier cantidad de "a" y cualquier cantidad de "b", tendremos que tener si o si 5 estados para cada simbolo "a", y de la misma manera 5 estados para cada simbolo "b" ya que a y b estan elevados al mismo exponente, tendremos que acerlo de esa manera porque el automata no tiene una manera de recordar cuantas veces repetimos "a" anteriormente para hacerlo de igual manera con "b"
Dijimos anteriormente que un lenguaje regular puede ser infinito,, y a ese lenguaje se lo puede representar por un automata finito.
asi que, que pasa si hacemos ese lenguaje aⁿbⁿ en un lenguaje infinito? siendo "n"=0, 1, 2, 3..... hasta el infinito?
en ese caso tendriamos tantos estados que seria imposible construirlo, ya que como dije, el automata no tiene una memoria que le diga cuantas veces se repitio cada simbolo...
Un automata de este tipo, que describe gramaticas de tipo 3, con estados finitos, transiciones, y estados de aceptacion, haceptan si o si cualquier lenguaje regular nada mas, si hay un lenguaje que no puede ser representado por estos, es porque no es regular
Vamos a ver como se puede saber si un lenguaje infinito es regular, de una manera mas formal.
el lema del bombeo dice que, si un lenguaje "L" es regular, entonces existe un numero entero P>=0
y que cualquier cadena w del lenguaje L de longitud mayor o igual a P, puede ser partida en 3 cadenas diferentes, asi: w = xyz.
pero para dividir una cadena en 3 subcadenas, se deben cumplir las siguientes condiciones:
1) las cadenas "xy" juntas, deben formar en total una cadena de longitud menor o igual a "P"
2) la cadena y tiene que ser de longitud mayor o igual a 1
3) siendo "n" cualquier numero natural, si elevamos la cadena "w" de esta manera xyⁿz, obtenemos otra cadena que tambien pertenece al lenguaje
por ejemplo:
tenemos el lenguaje descrito por la siguiente expresion : abⁿa
como ya sabemos, el valor de "n" puede ser cualquiera, este lenguaje es infinito, pero no sabemos si es regular, para eso deberia cumplir las propiedades.
elejimos un valor para P por ejemplo, P = 4
ahora elejimos una cadena de ese lenguaje que contenga igual o mas simbolos que P
ejemplo, la cadena -----> w = abba
esta cadena debemos dividirla en tres subcadenas xyz
siguiendo las condiciones, podemos dividir la palabra w = abba en...
x=ab y=b z=a
ahora realizamos esto, xyⁿz, le ponemos un valor a "n" por ej. n=3
si nosotros escogemos un valor cualquiera de "n" tal que xyⁿz, deberia resultar en otra cadena que tambien pertenece al mismo lenguaje, y si no es asi, no es un lenguaje regular.
resultaria en una nueva cadena w = abbbba
si ven, la nueva cadena tambien pertenece al lenguaje L = abⁿa, cumple la propiedad de bombeo, entonces es regular.
vamos a hacer de la misma manera con la expresion aⁿbⁿ
elegimos un valor de P. P = 5
una cadena de ese lenguaje con 5 o mas simblos, podria ser w = aaabbb
la dividimos en 3 cadenas siguiendo las condiciones. x=a y=aab z=bb
resolvemos xyⁿz, teniendo en cuenta que "n" vale por ejemplo n=2
la cadean resultante seria w = aaabaabbb
como la cadena no pertenece al lenguaje aⁿbⁿ entonces no es regular.
En otro post explicare con que automatas se puede reconocer estos lenguajes no regulares e infinitos.
Comentarios
Publicar un comentario