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

• Datos: Q1059648
• Multimedia: Pumping lemmas / Q1059648