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.
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. ISBN0-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. ISBN0-321-32221-5. Chapter 6: Properties of Regular Languages pp. 205-210
Datos:Q1059648
Multimedia:Category:Pumping lemmas
Febrero 27, 2022
lema, bombeo, teoría, lenguajes, formales, teoría, computación, lema, bombeo, establece, lenguaje, cualquier, cadena, caracteres, menos, cierta, longitud, llamada, longitud, bombeo, contiene, sección, puede, eliminada, repetida, cualquier, número, veces, caden. En la teoria de lenguajes formales de la teoria de la computacion 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 seccion que puede ser eliminada o repetida cualquier numero de veces con la cadena resultante perteneciendo a ese lenguaje La prueba de este lema tipicamente requiere argumentos de conteo como los del principio del palomar Los dos ejemplos mas importantes son el lema de bombeo para lenguajes regulares y el lema del bombeo para gramaticas independientes del contexto El lema de Ogden es un segundo lema de bombeo mas fuerte para lenguajes libres de contexto Estos lemas pueden ser usados para determinar si un lenguaje no esta en una clase de lenguajes Sin embargo no pueden ser usados para determinar si un lenguaje esta en una clase puesto que satisfacer el lema del bombeo es una condicion necesaria pero no una suficiente para ser miembro de una clase Referencias EditarMichael 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 Category Pumping lemmas Obtenido de https es wikipedia org w index php title Lema del bombeo amp oldid 121943737, wikipedia, wiki, leyendo, leer, libro, biblioteca,
