Aaaaaa

OBJETIVO
Comprender qué es y para qué sirve el Lema de Bombeo para lenguajes regulares, así como saber determinar por medio de éste si un lenguaje es regular o no.
PROCEDIMIENTO
Para larealización de este proyecto, se usaron recursos como la computadora y el internet para poder investigar y apoyarme en documentos y libros electrónicos ya existentes que me ayudaron a terminar el trabajo.RESULTADOS
Lema de bombeo para lenguajes regulares
¿QUIÉN LO DEFINIÓ?
El lema del bombeo fue enunciado por primera vez por Y. Bar-Hillel, M. Perles y E. Shamir en 1961.{text:bibliography-mark}
¿QUÉ DICE EL LEMA DE BOMBEO?
Para todo lenguaje regular L (sobre un alfabeto dado ) existe una constante n  N, llamada la constante del bombeo para L, tal que toda palabra w  L, con |w |>= n, satisface la siguiente propiedad:
w se puede descomponer como w = uvx, con | uv |= 0 se tiene uv^(i)x  L.
{draw:frame}
Tanto u como x pueden ser la cadena vacía, pero v ≠.
Lapalabra v (o la parte central) se puede bombear cero o más veces en el sentido de que uv^(i)x es aceptada por L, i >= 0. {text:bibliography-mark}
{draw:frame}
¿PARA QUÉ SIRVE?
El llamadoLema de Bombeo es una propiedad de los lenguajes regulares que es muy útil para demostrar que ciertos lenguajes no son regulares. {text:bibliography-mark}
EJEMPLOS DONDE SE DEMUESTRA QUE NO SONREGULARES
I.-
Podemos usar el lema del bombeo para demostrar que el lenguaje L = {a^(i)b^(i) : i >= 0} no es un lenguaje regular.
Demostración: Sea L es un lenguaje regular, entonces existe unaconstante de bombeo n  N. Sea w = a^(n)b^(n)  L, | w = a^(n)b^(n) |>= n.
Descomponemos w = uvx, | v |>= 1, | uv |= 0,
v = a^(s), s >= 1
w = a^(n)b^(n) = uvx
Entonces:
a^(n)b^(n) =a^(r)a^(s)x
x = a^(n-r-s)b^(n)
Ahora bombeamos v y se supone que uv^(i)x  L para i >= 0
Sea i = 0
ux = a^(r)a^(n-r-s)b^(n) = a^(n-s)b^(n)
Por el lema del bombeo uv^(i)x  L para i >= 0....