Hi ha dos lemes de bombeig, que es defineixen per a 1. Llenguatges regulars i 2. Context - Llenguatges lliures Pumping Lema per a llenguatges normals Per a qualsevol llenguatge regular L, existeix un nombre enter n, tal que per a tot x ? L amb |x| ? n, existeix u, v, w ? ?^*, tal que x = uvw, i (1) |uv| ? n (2) |v| ? 1 (3) per a tots i ? 0: UVⁱw? L En termes simples, això vol dir que si una cadena v és 'bombada', és a dir, si v s'insereix qualsevol nombre de vegades, la cadena resultant encara roman a L. El lema de bombeig s'utilitza com a prova de la irregularitat d'un llenguatge. Així, si una llengua és regular, sempre satisfà el lema de bombeig. Si hi ha almenys una corda feta de bombeig que no estigui en L, llavors L segurament no és regular. El contrari d'això pot no ser sempre cert. És a dir, si Pumping Lemma es compleix, no vol dir que el llenguatge sigui regular.

Per exemple, demostrem L₀₁= n ? 0 és irregular. Suposem que L és regular, aleshores per Pumping Lema segueixen les regles anteriors. Ara, siguem x ? L i |x| ? n. Així doncs, per Pumping Lema, existeix u, v, w tal que (1) – (3) es compleix. Mostrem que per a tot u, v, w, (1) – (3) no es compleix. Si (1) i (2) es mantenen, aleshores x = 0ⁿ1ⁿ= uvw amb |uv| ? n i |v| ? 1. Per tant, u = 0^a, v = 0^b, w = 0^c1ⁿon: a + b? n, b? 1, c? 0, a + b + c = n Però, aleshores (3) falla per i = 0 uv⁰w = uw = 0^a0^c1ⁿ= 0^{a + c}1ⁿ? L, ja que a + c ? n.

Pumping Lema per a llenguatges sense context (CFL) Pumping Lema per a CFL estableix que per a qualsevol Llenguatge Lliure de Context, és possible trobar dues subcadenes que es poden 'bombar' qualsevol nombre de vegades i encara estar en el mateix idioma. Per a qualsevol llenguatge L, dividim les seves cordes en cinc parts i bombem la segona i la quarta subcadena. Pumping Lemma, aquí també, s'utilitza com una eina per demostrar que un llenguatge no és CFL. Perquè, si una cadena no compleix les seves condicions, llavors el llenguatge no és CFL. Així, si L és un CFL, existeix un nombre enter n, tal que per a tot x ? L amb |x| ? n, existeix u, v, w, x, y ? ?^*, tal que x = uvwxy, i (1) |vwx| ? n (2) |vx| ? 1 (3) per a tots i ? 0: UVⁱwxⁱi ? L

Per a l'exemple anterior, 0ⁿ1ⁿés CFL, ja que qualsevol corda pot ser el resultat del bombeig a dos llocs, un per a 0 i un altre per a 1. Provem, L₀₁₂= n ? 0 no està lliure de context. Suposem que L està lliure de context i, per Pumping Lema, segueixen les regles anteriors. Ara, siguem x ? L i |x| ? n. Per tant, mitjançant el bombeig del lema, existeix u, v, w, x, y tal que (1) – (3) es compleix. Mostrem que per a tot u, v, w, x, y (1) – (3) no es compleixen. Si (1) i (2) es mantenen, aleshores x = 0ⁿ1ⁿ2ⁿ= uvwxy amb |vwx| ? n i |vx| ? 1. (1) ens diu que vwx no conté tant 0 com 2. Per tant, o vwx no té 0 o vwx no té 2. Per tant, tenim dos casos a considerar. Suposem que vwx no té zeros. Per (2), vx conté un 1 o un 2. Així, uwy té ‘n’ 0’s i uwy té menys que ‘n’ 1’s o té menys que ‘n’ 2’s. Però (3) ens diu que uwy = uv⁰wx⁰i? L. Per tant, uwy té un nombre igual de 0, 1 i 2 ens dóna una contradicció. El cas en què vwx no té 2 és similar i també ens dóna una contradicció. Per tant, L no està lliure de context. Font: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Introducció a la teoria dels autòmats, els llenguatges i la computació.

Aquest article ha estat contribuït per Nirupam Singh .