Lema De Bombeo.pdf 5w6m1s

Lema de Bombeo

Bayron Rubén De León Pérez 12-0542 Josué Augusto Puntiel Mena 13-0972 Profesora Rina Familia Lenguajes Formales y Teoría de Autómatas

Universidad Iberoamericana (UNIBE) Santo Domingo, República Dominicana 25 de Febrero del 2014|

Índice Introducción …………………………………………………………………………………..…...…… 3 Lenguaje Regular ………………………………………………………………………………..……… 4 Importancia de los Lenguajes Regulares ……………………………………………………………… 5 Cómo Demostrar que un Lenguaje no es Regular …………………………………………………… 5 El lema de bombeo para los lenguajes regulares ………………………………………………..…… 5 Teorema……………………………………………………………………………………………...…… 6 Demostración de que un lenguaje no es regular ……………………………………………………… 7 Ejemplo de demostración de que un lenguaje no es regular …………………………………...…… 8 El Lema de Bombeo para los Lenguajes Regulares ……………………………………….………… 9 Demostración…………………………………………………………………………………...…...…… 9 El Lema de Bombeo como un juego entre adversarios ……………………………………..……… 11 Aplicaciones del Lema de Bombeo ……………………………………………………………..…… 11 Definición de las Gramáticas Independientes del Contexto………………………………..………. 12 El Lema de Bombeo para lenguajes independientes del contexto ………………………………… 13 El Tamaño de los Árboles de Derivación……………………………………………………….…… 14 Enunciado del Lema de Bombeo ………………………………………………………………..…… 15 Demostración……………………………………………………….……………………………...…… 15 Conclusión……………………………………………………..…………………………………..…… 17 Referencias………………………………………………………………………..………………..…… 18

Introducción La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”. En las décadas de los años cuarenta y cincuenta, una serie de investigadores estudiaron las máquinas más simples, las cuales todavía hoy denominamos “autómatas finitos”. Originalmente, estos autómatas se propusieron para modelar el funcionamiento del cerebro y, posteriormente, resultaron extremadamente útiles para muchos otros propósitos.

Todos estos desarrollos teóricos afectan directamente a lo que los expertos en computadoras hacen. Algunos de los conceptos, como el de autómata finito y determinados tipos de gramáticas formales, se emplean en el diseño y la construcción de importantes clases de software.

El lema de bombeo para lenguajes regulares enuncia una propiedad que cumplen todos los lenguajes regulares infinitos (y también algunos lenguajes que no son 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.

Lenguaje Regular Se dice que un lenguaje es regular si y sólo si se cumple cualquiera de las siguientes proposiciones: 

Tiene al menos una gramática regular G que lo produce.



Puede ser reconocido por un autómata finito A.



Existe una expresión regular Er que representa a todas las cadenas de L. Lenguaje regular. En Lingüística, Matemáticas e Informática y en la jerarquía de

Chomsky se refiere a los lenguajes de tipo 3, aquellos que pueden representarse mediante gramáticas regulares, autómatas finitos o expresiones regulares.

Son los lenguajes formales más simples, con los mecanismos de representación y reconocimiento más estudiados. Su aplicación práctica en la teoría y construcción de intérpretes y compiladores de lenguajes

de

programación o

de especificación o formato de información, especialmente como microcomponentes del analizador lexicográfico que detecta los tókenes como constantes numéricas, cadenas de texto, operadores, palabras reservadas (keywords), separadores, etc. Pero también se puede apreciar su uso en máquinas expendedoras, teléfonos públicos, calculadoras y otros artefactos electromecánicos. También puede realizarse una definición recursiva-constructiva de los lenguajes regulares mediante el álgebra de lenguajes formales.

Un lenguaje regular sobre un alfabeto T ó LR(T) es: 

El lenguaje vacío {}.



El lenguaje conformado por la cadena vacía



Un lenguaje {x} conformado por un único símbolo x de T.



Si A y B son

lenguajes

lenguajes), Archivo:

A

regulares unión

o lenguaje trivial.

sobre T,

B.gif (Unión

entonces AB (Concatenación

de

de

de

lenguajes), A* (Clausura

lenguaje o Estrella de Kleene) son también lenguajes regulares sobre T. 

Cualquier otro lenguaje que pueda obtenerse a partir de 1 a 4.

Importancia de los Lenguajes Regulares La existencia y formalización de los lenguajes regulares (LR) y su vinculación con otros artefactos lingüísticos-matemáticos ya bien formalizados, estudiados e incluso llevados a la práctica ha sido de vital importancia en el ulterior desarrollo de los mecanismos de procesamiento de lenguajes de computadora, fundamentalmente en los analizadores lexicográficos gracias a la posibilidad de derivar el reconocimiento de los LR mediante autómatas finitos que son fáciles de implementar computacionalmente con mecanismos simples y rápidos, óptimos en la obtención de parsers veloces y robustos que a su vez le ofrecen a los desarrolladores información detallada de los errores léxicos, sintácticos e incluso advierten sobre errores semánticos. Lo mismo sucede por ejemplo con las expresiones regulares implementadas ya en muchos Lenguaje de programación de propósito general modernos que permiten a los desarrolladores de lenguajes mecanismos muy eficientes para la obtención intuitiva de partes de compiladores que reconocen los tókenes o partículas lexicales del código fuente como fase del proceso completo de interpretación o compilado, según sea el caso Cómo Demostrar que un Lenguaje no es Regular No todo lenguaje es un lenguaje regular. El lema de bombeo permite demostrar que determinados lenguajes no son regulares. El lema de bombeo para los lenguajes regulares

El lema de bombeo para lenguajes regulares enuncia una propiedad que cumplen todos los lenguajes regulares infinitos (y también algunos lenguajes que no son regulares). Gracias a este lema podremos demostrar que ciertos lenguaje 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. Considerando el lenguaje L01 = {0n1n | n≥1}. Este lenguaje contiene las cadenas 01, 0011, 000111, etc., que constan de uno o más ceros seguidos de un número igual de unos.

Establecemos que L01 no es un lenguaje regular. El argumento intuitivo es que si L01 fuera regular, entonces L01 sería el lenguaje de algún AFD A, que tendría un determinado número de estados, digamos k estados. Imagine que este autómata recibe k ceros como entrada. Después de recibir los k+1 prefijos de la entrada: ε,0,00,...,0k se encontrará en un cierto estado. Dado que sólo existen k estados distintos, el principio del juego de las sillas nos dice que después de leer dos prefijos diferentes, por ejemplo, 0i y 0j, A tiene que encontrarse en el mismo estado, por ejemplo q. Sin embargo, en lugar de esto, suponemos que después de leer i o j ceros, el autómata A comienza a recibir unos como entrada. Después de recibir i unos, debe aceptar si previamente ha recibido i ceros, pero no si ha recibido j ceros. Puesto que estaba en el estado q cuando comenzaron a llegar unos, no puede “recordar” si había recibido i o j ceros, por lo que podemos “engañar” a A y hacerle cometer un error: aceptar cuando no debe hacerlo o no aceptar cuando debería hacerlo.

El argumento anterior es de carácter informal, pero puede precisarse. Sin embargo, puede llegarse a la misma conclusión, que el lenguaje L01 no es un lenguaje regular, utilizando un resultado general de la forma siguiente.

Teorema

El lema de bombeo para lenguajes regulares) Sea L un lenguaje regular. Existe entonces una constante n (que depende de L) tal que para toda cadena w perteneciente a L con |w| ≥n, podemos descomponer w en tres cadenas,

W = xyz, tales que: 

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



|xy| <= n



Para cualquier k ≥ 0, la cadena xy z pertenece a L.

k

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 z ∈ L

k

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.

Demostración de que un lenguaje no es regular

Dado que para todo lenguaje regular infinito se cumple el lema de bombeo, si se da un lenguaje infinito y se demuestra que para él no se cumple, se habra 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

∃ k ≥ 0 / xy z ∉ L

Es importante hacer notar que en esta demostración, por reducción al absurdo, de que un lenguaje no es regular, los cuantificadores existenciales “para todo” y “existe” están alternados al revés que en el enunciado del lema. Esto es, intuitivamente, porque se esta demostrando lo contrario que el lema de bombeo: éste enuncia una propiedad que cumplen todos los lenguajes regulares y la demostración precedente demuestra que un lenguaje no es regular, o sea que no cumple esa propiedad.

Ejemplo de demostración de que un lenguaje no es regular Sea el lenguaje L = {a2nbn | n ≥ 0}. Demostrar que L no es regular.

Suponiendo que el lenguaje es regular. Si lo es, y como es infinito, para él se cumplirá el lema de bombeo. Sea por tanto n ∈ N la constante del lema de bombeo para L (constante que no se conoce).

Eligiendo una palabra que pertenezca a L y de longitud mayor o igual a n: 2n n

w = a b , tenemos que w ∈ L y |w| = 3n y por tanto |w| ≥ n, sea cual sea n.

El Lema de Bombeo para los Lenguajes Regulares Considerando el lenguaje L01 = {0n1n | n ≥ 1}. Este lenguaje contiene las cadenas 01, 0011, 000111, etc., que constan de uno o más ceros seguidos de un número igual de unos. Establecemos que L01 no es un lenguaje regular. El argumento intuitivo es que si L01 fuera regular, entonces L01 sería el lenguaje de algún AFD A, que tendría un determinado número de estados, digamos k estados. Imaginar que este autómata recibe k ceros como entrada. Después de recibir los k+1 prefijos de la entrada: ε ,0,00, . . . ,0k se encontrará en un cierto estado. Dado que sólo existen k estados distintos, el principio del juego de las sillas nos dice que después de leer dos prefijos diferentes, por ejemplo, 0i y 0j, A tiene que encontrarse en el mismo estado, por ejemplo q.

Sin embargo, en lugar de esto, se supone que después de leer i o j ceros, el autómata A comienza a recibir unos como entrada. Después de recibir i unos, debe aceptar si previamente ha recibido i ceros, pero no si ha recibido j ceros. Puesto que estaba en el estado q cuando comenzaron a llegar unos, no puede “recordar” si había recibido i o j ceros, por lo que podemos “engañar” a A y hacerle cometer un error: aceptar cuando no debe hacerlo o no aceptar cuando debería hacerlo. El argumento anterior es de carácter informal, pero puede precisarse. Sin embargo, puede llegarse a la misma conclusión, que el lenguaje L01 no es un lenguaje regular, utilizando un resultado general de la forma siguiente.

Demostración

Supongamos que L es regular. Entonces L =L(A) para algún AFD A. Supongamos que A tiene n estados. Consideremos ahora cualquier cadena w de longitud n o mayor, por ejemplo w = a1a2 · · ·am, donde m ≥ n y cada ai es un símbolo de entrada. Para i = 0,1, . . . ,n definimos el estado pi como _ δ (q0,a1a2 · · ·ai), donde δ es la función de transición de A y q0 es el estado

inicial de A. Es decir, pi es el estado en que se encuentra A después de leer los primeros i símbolos de w. Observe que p0 = q0.

Por el principio del juego de las sillas, no es posible que los n+1 pi para i = 0,1, . . . ,n sean diferentes, ya que sólo existen n estados distintos. Por tanto, podemos determinar dos enteros distintos i y j, con 0 ≤ i< j ≤ n, tales que pi = pj . Ahora podemos descomponer w = xyz como sigue:

1. x = a1a2 · · ·ai. 2. y = ai+1ai+2 · · ·aj . 3. z = aj+1aj+2 · · ·am.

Es decir, x lleva a pi una vez; y lleva desde pi a pi de nuevo (ya que pi también es pj) y z es el resto de w.

Considerando ahora lo que ocurre si el autómata A recibe la entrada xykz para cualquier k ≥ 0. Si k = 0, entonces el autómata va desde el estado inicial q0 (que también es p0) hasta pi para la entrada x. Puesto que pi también es pj , al leer la entrada z. Por tanto, A acepta xz.

Si k > 0, entonces A va desde q0 hasta pi para la entrada x, va en círculo desde pi hasta pi k veces para la entrada yk, y luego pasa al estado de aceptación para la entrada z. Por tanto, para cualquier k ≥ 0, A también acepta xykz; es decir, xykz pertenece a L.

El Lema de Bombeo como un juego entre adversarios Un teorema cuya proposición implica varias alternativas de cuantificadores “para todo” y “existe” puede interpretarse como un juego entre dos personas. El lema de bombeo es un ejemplo importante de este tipo de teorema, ya que implica cuatro identificadores diferentes: “para todos los lenguajes L existe n tal que para toda w perteneciente a L con |w| ≥ n existe xyz igual a w tal que · · · ”. Podemos interpretar la aplicación del lema de bombeo como un juego en el que:

1. El jugador 1 selecciona el lenguaje L para demostrar que no es regular. 2. El jugador 2 selecciona n, pero no revela al jugador 1 lo que vale n; el jugador 1 debe plantear el juego para todos los n posibles. 3. El jugador 1 selecciona w, que puede depender de n y cuya longitud tiene que ser al menos igual a n. 4. El jugador 2 divide w en x, y y z, teniendo en cuenta las restricciones que se estipulan en el lema de bombeo; y _=ε y |xy| ≤ n. De nuevo, el jugador 2 no dice al jugador 1 qué valores tienen x, y y z, aunque debe respetar las restricciones. 5. El jugador 1 “gana” eligiendo un valor de k, que puede ser una función de n, x,y y z, tal que xykz no pertenezca a L.

Aplicaciones del Lema de Bombeo Demostrar que el lenguaje Leq que consta de todas las cadenas con un número igual de ceros que de unos (en ningún orden en particular) no es un lenguaje regular. Siendo el jugador 1 y se debe enfrentar con cualquier elección que haga el jugador 2. Suponiendo que n es la constante que existiría si Leq fuera regular, de acuerdo con el lema de bombeo; es decir, el “jugador 2” elige n. El jugador 1 selecciona w = 0n1n, es decir, n ceros seguidos de n unos, una cadena que seguramente pertenece a Leq.

Ahora el “jugador 2” divide w en xyz. Todo lo que sabemos es que y _= ε y |xy| ≤ n. Sin embargo, dicha información es muy útil y “gana” de la forma siguiente. Dado que |xy| ≤ n y que xy procede del principio de w, se sabe que x e y constan sólo de ceros. El lema de bombeo nos dice que xz pertenece a Leq, si Leq es regular. Esta conclusión corresponde al caso en que k = 0 en el lema de bombeo. Sin embargo, xz tiene n unos, ya que todos los unos de w están en z. Pero xz también tiene menos de n ceros, porque hemos perdido los ceros de y. Puesto que y _= ε , se sabe que no puede haber más de n−1 ceros entre x y z. Por tanto, después de suponer que Leq es un lenguaje regular, se ha demostrado un hecho que se sabe que es falso, que xz pertenece a Leq.

Se Tiene una demostración por reducción al absurdo del hecho de que Leq no es regular.

Definición de las Gramáticas Independientes del Contexto

Existen cuatro componentes importantes en una descripción gramatical de un lenguaje:

1. Un conjunto finito de símbolos que forma las cadenas del lenguaje que se está definiendo. Este conjunto era {0,1} en el ejemplo de los palíndromos que acabamos de ver. Denominamos a este conjunto alfabeto terminal o alfabeto de símbolos terminales. 2. Un conjunto finito de variables, denominado también en ocasiones símbolos no terminales o categorías sintácticas. Cada variable representa un lenguaje; es decir, un conjunto de cadenas. En el ejemplo anterior, sólo había una variable, P, que hemos empleado para representar la clase de palíndromos del alfabeto {0,1}. 3. Una de las variables representa el lenguaje que se está definiendo; se denomina símbolo inicial. Otras variables representan las clases auxiliares de cadenas que se emplean para definir el lenguaje del símbolo inicial. En el ejemplo anterior, la única variable, P, también es el símbolo inicial. 4. Un conjunto finito de producciones o reglas que representan la definición recursiva de un lenguaje. Cada producción consta de:

a) Una variable a la que define (parcialmente) la producción. Esta variable a menudo se denomina cabeza de la producción. b) El símbolo de producción→. c) Una cadena formada por cero o más símbolos terminales y variables. Esta cadena, denominada cuerpo de la producción, representa una manera de formar cadenas pertenecientes al lenguaje de la variable de la cabeza. De este modo, dejamos los símbolos terminales invariables y sustituimos cada una de las variables del cuerpo por una cadena que sabemos que pertenece al lenguaje de dicha variable.

Los cuatro componentes que acabamos de describir definen una gramática independiente del contexto, (GIC), o simplemente una gramática, o en inglés CFG, context-free grammar. Se representa una GIC G mediante sus cuatro componentes, es decir, G = (V,T,P,S), donde V es el conjunto de variables, T son los símbolos terminales, P es el conjunto de producciones y S es el símbolo inicial. El Lema de Bombeo para lenguajes independientes del contexto Si se considera el lenguaje de los palíndromos. Un palíndromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda, como por ejemplo, otto o dabalearrozalazorraelabad (“Dábale arroz a la zorra el abad”). Dicho de otra manera, la cadena w es un palíndromo si y sólo si w = wR. Para hacer las cosas sencillas, consideremos únicamente los palíndromos descritos con el alfabeto {0,1}. Este lenguaje incluye cadenas del tipo 0110, 11011 y ε , pero no cadenas como 011 o 0101.

Es fácil verificar que el lenguaje Lpal de los palíndromos formados por ceros y unos no es un lenguaje regular. Para ello, utilizamos el lema de bombeo. Si Lpal es un lenguaje regular, sea n la constante asociada y consideremos el palíndromo w = 0n10n. Si Lpal es regular, entonces podemos dividir w en w = xyz, tal que y consta de uno o más ceros del primer grupo. Por tanto, xz, que también tendría que pertenecer a Lpal si Lpal fuera regular, tendría menos ceros a la izquierda del único 1 que los que tendría a la derecha del mismo. Por tanto, xz no puede ser un palíndromo. Luego hemos llegado a una contradicción de la hipótesis establecida, que Lpal es un lenguaje regular.

Existe una definición recursiva y natural que nos dice cuándo una cadena de ceros y unos pertenece a Lpal . Se parte de un caso básico estableciendo que unas cuantas cadenas obvias pertenecen a Lpal , y luego se aplica la idea de que si una cadena es un palíndromo, tiene que comenzar y terminar con el mismo símbolo. Además, cuando el primer y último símbolos se eliminan, la cadena resultante también tiene que ser un palíndromo. Es decir, Base. ε , 0 y 1 son palíndromos. Paso Inductivo. Si w es un palíndromo, también lo son 0w0 y 1w1. Ninguna cadena es un palíndromo de ceros y unos, a menos que cumpla el caso base y esta regla de inducción.

Una gramática independiente del contexto es una notación formal que sirve para expresar las definiciones recursivas de los lenguajes. Una gramática consta de una o más variables que representan las clases de cadenas, es decir, los lenguajes. En este ejemplo sólo necesitamos una variable P, que representa el conjunto de palíndromos; ésta es la clase de cadenas que forman el lenguaje Lpal . Existen reglas que establecen cómo se construyen las cadenas de cada clase. La construcción puede emplear símbolos del alfabeto, cadenas que se sabe que pertenecen a una de las clases, o ambos elementos. El teorema, conocido como “lema de bombeo para lenguajes independientes del contexto”, establece que en cualquier cadena lo suficientemente larga de un LIC, es posible encontrar a los sumo dos subcadenas cortas y muy próximas que pueden “bombearse” en tándem. Es decir, se puede repetir ambas cadenas i veces, para cualquier entero i, y la cadena resultante pertenecerá al lenguaje. El Tamaño de los Árboles de Derivación

El primer paso para obtener un lema de bombeo para los LIC consiste en examinar la forma y el tamaño de los árboles de derivación. Una de las aplicaciones de la FNC es transformar los árboles de derivación en árboles binarios. Estos árboles tienen propiedades interesantes y aquí vamos a aprovechar una de ellas.

Enunciado del Lema de Bombeo El lema de bombeo para los LIC es bastante similar al lema de bombeo para los lenguajes regulares, pero se descomponen cada cadena z del LIC L en cinco partes y bombeamos en tándem la segunda y la cuarta partes.

Lema de bombeo para los lenguajes independientes del contexto. Sea L un LIC. Entonces existe una constante n tal que si z es cualquier cadena de L tal que |z| es al menos n, entonces podemos escribir z = uvwxy, sujeta a las siguientes condiciones: 1. |vwx| ≤ n. Es decir, la parte central no es demasiado larga. 2. vx _= ε . Puesto que v y x son las partes que se van a “bombear”, esta condición establece que al menos una de las cadenas que se van a bombear no tiene que ser vacía. 3. Para todo i ≥ 0, uviwxiy pertenece a L. Es decir, las dos cadenas v y x pueden “bombearse” cualquier número de veces, incluyendo cero, y la cadena resultante pertenecerá a L.

Demostración El primer paso consiste en determinar una gramática G en la forma normal de Chomsky para L. Técnicamente, no se puede determinar tal gramática si L es el LIC /0 o {ε }. Sin embargo, si L = /0 entonces el enunciado del teorema, que establece que una cadena z de L no puede violarse, ya que no existe dicha cadena z en / 0. Además la gramática en la FNC G generará L−{ε }, pero de nuevo esto no es importante, ya que sin dudas se seleccionara n > 0, en cuyo caso z no puede ser ε de ninguna manera.

Se parte de una gramática en la FNC G = (V,T,P,S) tal que L(G) = L−{ε } y suponiendo que G tiene m variables. Se Elige n = 2m. A continuación, se supone que z de L tiene una longitud al menos igual a n. Un árbol de derivación así no puede tener un resultado z, porque z es demasiado larga. Por tanto, cualquier árbol de derivación con resultado z tiene un camino de longitud al menos igual a m+1.

La cadena w es el resultado del subárbol con raíz en Aj . Las cadenas v y x son las cadenas a la izquierda y a la derecha, respectivamente, de w en el resultado del subárbol más largo con raíz en Ai. Observe que, dado que no existen producciones unitarias, v y x no pueden ser ambas ε , aunque una sí podría serlo. Por último, u e y son aquellas partes de z que están a la izquierda y a la derecha, respectivamente, del subárbol con raíz en Ai.

Si Ai = Aj = A, entonces se puede construir nuevos árboles de derivación a partir del árbol original. Primero se puede reemplazar el subárbol con raíz en Ai, lo que da como resultado vwx, por el subárbol con raíz en Aj , que tiene como resultado w. La razón de poder hacer esto es que ambos árboles tienen A como raíz.

El detalle que queda es la condición (1), que establece que |vwx| ≤ n. Sin embargo, elegimos Ai cerca de la parte inferior del árbol; es decir, k−i ≤ m. Por tanto, el camino más largo en el subárbol con raíz en Ai no es mayor que m+1. De acuerdo con el Teorema 7.17, el subárbol con raíz en Ai tiene un resultado cuya longitud no es mayor que 2m = n.

Conclusión El lema de bombeo para las expresiones regulares es una simplificación de un resultado de los lenguajes independientes del contexto obtenido por Bar- Hillel, Perles y Shamir

Si un lenguaje es regular, entonces toda cadena lo suficientemente larga del lenguaje tiene una subcadena no vacía que puede ser “bombeada”, es decir, repetida cualquier número de veces siempre y cuando las cadenas resultantes pertenezcan también al lenguaje. Este hecho puede utilizarse para demostrar que muchos lenguajes no son regulares. El lema de bombeo. En cualquier LIC, es posible encontrar, dentro de cualquier cadena lo suficientemente larga del lenguaje, una subcadena corta tal que los dos extremos de dicha subcadena puedan ser “bombeados” en tándem; es decir, cada uno de ellos puede repetirse el número de veces que se desee. Las dos cadenas que van a bombearse no pueden ser ambas ε . Este lema, y su versión más potente, conocida como el lema de Ogden permiten demostrar que muchos lenguajes no son independientes del contexto.

Referencias

Conocimiento con todos y para todos (S.F). Lenguaje Regular. Recuperado el 20 de Febrero del 2014 de: http://www.ecured.cu/index.php/Lenguaje_regular

Elena Jurado Málaga (2008). Teoría de Automatas. Recuperado el 22 de Febrero del 2014 de: http://campusvirtual.unex.es/ebooks/files/file/TeoriaAutomatas.pdf

Rubén Béjar Hernández (S.F). El lema de bombeo para lenguajes regulares. Recuperado el 21 de Febrero del 2014 de: http://webdiis.unizar.es/asignaturas/LGA

John E. Hopcroft (S.F). Teoría de autómatas, lenguajes y computación. Recuperado el 20 de Febrero

del

2014

de:

http://computacion.cs.cinvestav.mx/~efranco/docencia/teoriacomputacional/files/books/T eoriaDeAutomatas,lenguajesYComputacion-Hopcroft.pdf