Lema de bombeo

En la teoría de lenguajes formales , el lema de bombeo puede referirse a:

Lema de bombeo para lenguajes regulares , el hecho de que todas las cadenas suficientemente largas en dicho lenguaje tienen una subcadena que puede repetirse arbitrariamente muchas veces, generalmente se usa para demostrar que ciertos lenguajes no son regulares.
Lema de bombeo para lenguajes libres de contexto , el hecho de que todas las cadenas suficientemente largas en dicho lenguaje tienen un par de subcadenas que pueden repetirse arbitrariamente muchas veces, generalmente se usa para demostrar que ciertos lenguajes no son libres de contexto.
Lema de bombeo para lenguajes indexados
Lema de bombeo para lenguajes de árboles regulares

Véase también

Lema de Ogden , una versión más fuerte del lema de bombeo para lenguajes libres de contexto

Este artículo de índice de conjunto incluye una lista de elementos relacionados que comparten el mismo nombre (o nombres similares).
Si un enlace interno lo llevó aquí por error, puede cambiar el enlace para que apunte directamente al artículo deseado.