Lema del bombeo

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 eliminada o repetida cualquier número de veces, con la cadena resultante perteneciendo a ese lenguaje. La prueba de este lema típicamente requiere argumentos de conteo como los del principio del palomar.

Los dos ejemplos más importantes son el lema de bombeo para lenguajes regulares y el lema del bombeo para gramáticas independientes del contexto. El lema de Ogden es un segundo lema de bombeo, más fuerte, para lenguajes libres de contexto.

Estos lemas pueden ser usados para determinar si un lenguaje no está en una clase de lenguajes. Sin embargo, no pueden ser usados para determinar si un lenguaje está en una clase, puesto que satisfacer el lema del bombeo es una condición necesaria, pero no una suficiente, para ser miembro de una clase.

Referencias

  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.
  • Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN 0-321-32221-5.  Chapter 6: Properties of Regular Languages pp. 205-210

Wikimedia foundation. 2010.

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

Mira otros diccionarios:

  • 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… …   Wikipedia Español

  • Lema del bombeo para gramáticas independientes del contexto — Viene de Lema del bombeo: Sea un lenguaje libre de contexto. Entonces existe una constante tal que para toda palabra , con , existe una descomposición tal que …   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

  • Lema (matemáticas) — En matemáticas, un lema es una proposición demostrada, utilizada para establecer un teorema menor o una premisa auxiliar que forma parte de un teorema más general. El término proviene del griego λήμμα, que significa cualquier cosa que es recibida …   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

  • Gramáticas sensibles al contexto — Una gramática sensible al contexto es una gramática formal G = (N, Σ, P, S) tal que todas las producciones P son de la forma: αAβ → αγβ con A en N y α y β en (N U Σ)* y γ en (N U Σ)+, con la posibilidad de la regla lambda S → λ con λ, la cadena… …   Wikipedia Español

  • Arquímedes — Saltar a navegación, búsqueda Arquímedes de Siracusa (Griego antiguo: Άρχιμήδης) Filosofía de la Grecia Clásica Filosofía antigua …   Wikipedia Español

  • Nogales (Veracruz) — Nogales Escudo …   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”