Tuesday, April 18, 2006

El lema del Bombeo.

Me hube leido un articulo acerca del lema del bombeo para expresiones regulares de la Unviersidad de Zaragoza cuyos autores son Rubén Béjar Hernández y Pedro Javier Álvarez Pérez-Aradros.
(...)
O sea que para cualquier cadena de L lo bastante larga, siempre podremos encontrar una partición en tres subcadenas, con una no vacía en el medio (la y) que no está demasiado lejos del comienzo de la palabra, que podremos “bombear”; es decir, que si se repite la subcadena y cualquier número de veces, la cadena resultante también pertenecerá a L.
(...)
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.
Mi pregunta es si se podrá cumplir esa regla para espacios de estados de aceptación?
Parágrafo: Lo que esta en cursiva es material obtenido del articulo.

No comments: