Hay dos lemas de bombeo, que se definen para 1. Idiomas regulares y 2. Contexto: idiomas libres. Lema de bombeo para lenguajes regulares Para cualquier lenguaje regular L, existe un número entero n, tal que para todo x ? L con |x| ? n, existe u, v, w? ?^*, tal que x = uvw y (1) |uv| ? norte (2) |v| ? 1 (3) para todo i ? 0: ultravioletaⁱ¿w? L En términos simples, esto significa que si una cadena v se 'bombea', es decir, si v se inserta cualquier número de veces, la cadena resultante aún permanece en L. El lema de bombeo se utiliza como prueba de la irregularidad de un lenguaje. Por lo tanto, si un lenguaje es regular, siempre satisface el lema de bombeo. Si existe al menos una sarta hecha de bombeo que no está en L, entonces L seguramente no es regular. Es posible que lo contrario no siempre sea cierto. Es decir, si el lema de bombeo se cumple, no significa que el lenguaje sea regular.

Por ejemplo, demostremos L₀₁= norte ? 0 es irregular. Supongamos que L es regular, luego, mediante el lema de bombeo, se siguen las reglas dadas anteriormente. Ahora, sea x ? L y |x| ? norte. Entonces, según el lema de bombeo, existen u, v, w tales que (1) – (3) se cumplen. Demostramos que para todo u, v, w, (1) – (3) no se cumple. Si (1) y (2) se cumplen entonces x = 0^norte1^norte= uvw con |uv| ? norte y |v| ? 1. Entonces, u = 0^a,v = 0^b, w = 0^C1^nortedonde: a+b? n, b ? 1,c? 0, a + b + c = n Pero entonces (3) falla para i = 0 uv⁰w = uw = 0^a0^C1^norte= 0^a+c1^norte? L, ya que a + c ? norte.

Lema de bombeo para lenguajes libres de contexto (CFL) Pumping Lemma para CFL establece que para cualquier lenguaje L libre de contexto, es posible encontrar dos subcadenas que se pueden 'bombear' cualquier cantidad de veces y aún estar en el mismo idioma. Para cualquier idioma L, dividimos sus cadenas en cinco partes y bombeamos la segunda y cuarta subcadenas. Pumping Lemma, aquí también, se utiliza como herramienta para demostrar que un idioma no es CFL. Porque, si alguna cadena no cumple sus condiciones, entonces el lenguaje no es CFL. Por tanto, si L es una CFL, existe un número entero n, tal que para todo x ? L con |x| ? n, ¿existe u, v, w, x, y? ?^*, tal que x = uvwxy y (1) |vwx| ? norte (2) |vx| ? 1 (3) para todo i ? 0: ultravioletaⁱwxⁱy ? L

Para el ejemplo anterior, 0^norte1^nortees CFL, ya que cualquier cuerda puede ser el resultado de bombear en dos lugares, uno para 0 y otro para 1. Probemos, L₀₁₂= norte ? 0 no está libre de contexto. Supongamos que L no tiene contexto, luego, mediante Pumping Lemma, se siguen las reglas dadas anteriormente. Ahora, sea x ? L y |x| ? norte. Entonces, según el lema de bombeo, existen u, v, w, x, y tales que (1) – (3) se cumplen. Demostramos que para todo u, v, w, x, y (1) – (3) no se cumplen. Si (1) y (2) se cumplen entonces x = 0^norte1^norte2^norte= uvwxy con |vwx| ? norte y |vx| ? 1. (1) nos dice que vwx no contiene 0 y 2. Por lo tanto, vwx no tiene ceros o vwx no tiene 2. Así, tenemos dos casos a considerar. Supongamos que vwx no tiene ceros. Por (2), vx contiene un 1 o un 2. Por lo tanto, uwy tiene 'n' 0 y uwy tiene menos de 'n' 1 o menos de 'n' 2. Pero (3) nos dice que uwy = uv⁰wx⁰¿y? L. Entonces, uwy tiene el mismo número de 0, 1 y 2, lo que nos da una contradicción. El caso en el que vwx no tiene 2 es similar y también nos da una contradicción. Por tanto, L no está libre de contexto. Fuente: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introducción a la teoría, los lenguajes y la computación de autómatas.

Este artículo ha sido contribuido por Nirupam Singh .