Lema del bombeo para lenguajes regulares

Lema del bombeo para lenguajes regulares

En la teoría de lenguajes formales, el lema del bombeo para lenguajes regulares describe una propiedad esencial de todo lenguaje regular. Informalmente, dice que cualquier palabra suficientemente larga en un lenguaje regular puede ser bombeada - eso es, repetir una sección en la mitad de la palabra un número arbitrario de veces - para producir una nueva palabra que también pertenece al mismo lenguaje.

El lema de bombeo fue enunciado por primera vez por Y. Bar-Hillel, M. Perles, E. Shamir en 1961.[1] Es útil para demostrar que un lenguaje específico no es regular.

Enunciado formal

Sea L un lenguaje regular. Entonces existe un entero p\ge1 (al que llamaremos "longitud de bombeo" y que dependerá exclusivamente de L) tal que cualquier cadena w perteneciente a L, de longitud mayor o igual que p, puede ser escrita como w = xyz (p. ej. dividiendo w en tres subcadenas), de forma que se satisfacen las siguientes condiciones:

  1. |y| \ge 1
  2. |xy| \le p
  3. \forall i/\ i\ge0, xy^iz\in L

y es la subcadena que puede ser bombeada (borrada o repetida un número i de veces como se indica en (3), y la cadena resultante seguirá perteneciendo a L). (1) significa que la cadena y que se bombea debe tener como mínimo longitud uno. (2) significa que y debe estar dentro de los p primeros caracteres. No hay restricciones acerca de x o z.

Uso del lema

El lema del bombeo se usa a menudo para probar que un lenguaje particular no es regular: una demostración por reducción al absurdo (de que un lenguaje no es regular) puede consistir en encontrar una palabra (de una longitud requerida) en el lenguaje, que carece de la propiedad descrita en el lema del bombeo.

Por ejemplo, del lenguaje L = \{a^nb^n\} : n \ge 0 sobre el alfabeto σ = a,b puede demostrarse que no es regular como sigue:

Supongamos que L es regular. Sean w, x, y, z, p, e i como las descritas en el enunciado formal de arriba. Sea w \in L dado por w = apbp. Por el lema del bombeo, debe haber una descomposición w = xyz con |xy| \le p e |y| \ge 1 tales que xy^iz \in L  \forall i/\ i \ge 0. Si hacemos que | xy | = p y que | z | = p, entonces xy será la primera mitad de w, (las p aes). Como |y| \ge 1, y tiene una cantidad no nula de aes, y por tanto cualquier cadena bombeada como p. ej. xy2z tendrá un número mayor de aes que de bes y no pertenecerá al lenguaje L, lo que contradice el tercer punto del lema. La suposición de que L es regular debe ser incorrecta. Por tanto L no es regular.

Referencias

  1. Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Lema del bombeo — En la teoría de lenguajes formales de la teoría de la computación, el lema de bombeo establece que en un lenguaje, cualquier cadena de caracteres de por lo menos una cierta longitud (llamada longitud de bombeo), contiene una sección que puede ser …   Wikipedia Español

  • Bombeo — Saltar a navegación, búsqueda El término Bombeo se puede referir a: El manejo de una bomba El término hidraulico Estación de bombeo El término sobre armas Acción de bombeo El término Informático Lema del bombeo Lema del bombeo para lenguajes… …   Wikipedia Español

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

  • Lenguaje sensible al contexto — En las ciencias de la computación, un lenguaje sensible al contexto es un [[lenguaje formal] que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática… …   Wikipedia Español

  • Lenguaje regular — Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades: Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”