Yra dvi siurbimo lemos, kurios yra apibrėžtos 1. įprastoms kalboms ir 2. kontekstui – laisvosioms kalboms. Pumping Lema įprastoms kalboms Bet kuriai taisyklingajai kalbai L yra sveikas skaičius n, kad visiems x ? L su |x| ? n, egzistuoja u, v, w ? ?^*, kad x = uvw ir (1) |uv| ? n (2) |v| ? 1 (3) visiems i ? 0: uvⁱw ? L Paprasčiau tariant, tai reiškia, kad jei eilutė v yra „pumpuojama“, t. y. jei v įterpiama bet kokį skaičių kartų, gauta eilutė vis tiek lieka L. Pumping Lemma naudojama kaip kalbos netaisyklingumo įrodymas. Taigi, jei kalba yra taisyklinga, ji visada patenkina siurbimo lemą. Jei yra bent viena eilutė, pagaminta iš siurbimo, kurios nėra L, tai L tikrai nėra taisyklinga. Priešingai, ne visada gali būti tiesa. Tai yra, jei galioja Pumping Lemma, tai nereiškia, kad kalba yra taisyklinga.

Pavyzdžiui, įrodykime L₀₁= n? 0 yra nereguliarus. Darykime prielaidą, kad L yra reguliarus, tada Pumping Lemma vadovaujasi aukščiau pateiktomis taisyklėmis. Dabar tegul x? L ir |x| ? n. Taigi, pumpuojant lemą, egzistuoja u, v, w, kad (1) – (3) galioja. Rodome, kad visiems u, v, w, (1) – (3) negalioja. Jei (1) ir (2) galioja, tada x = 0ⁿ1ⁿ= uvw su |uv| ? n ir |v| ? 1. Taigi, u = 0^a, v = 0^b, w = 0^c1ⁿkur: a + b? n, b? 1, c? 0, a + b + c = n Bet tada (3) nepavyksta, kai i = 0 uv⁰w = uw = 0^a0^c1ⁿ= 0^{a + c}1ⁿ? L, nes a + c ? n.

Pumping Lemma be konteksto kalboms (CFL) Pumping Lemma for CFL teigia, kad bet kuriai be konteksto kalbai L galima rasti dvi eilutes, kurias galima „siurbti“ bet kokį skaičių kartų ir vis tiek būti ta pačia kalba. Bet kuriai kalbai L suskaidome jos eilutes į penkias dalis ir pumpuojame antrąją bei ketvirtąją eilutes. Pumping Lemma čia taip pat naudojama kaip priemonė įrodyti, kad kalba nėra CFL. Nes jei kuri nors eilutė neatitinka jos sąlygų, kalba nėra CFL. Taigi, jei L yra CFL, egzistuoja sveikas skaičius n, kad visiems x ? L su |x| ? n, egzistuoja u, v, w, x, y? ?^*, kad x = uvwxy ir (1) |vwx| ? n (2) |vx| ? 1 (3) visiems i ? 0: uvⁱwxⁱir ? l

Aukščiau pateiktame pavyzdyje 0ⁿ1ⁿyra CFL, nes bet kuri eilutė gali būti siurbimo dviejose vietose rezultatas: viena – 0, kita – 1. Įrodykime, L₀₁₂= n? 0 nėra be konteksto. Tarkime, kad L yra be konteksto, tada Pumping Lemma vadovaujasi aukščiau pateiktomis taisyklėmis. Dabar tegul x? L ir |x| ? n. Taigi, pumpuojant lemą, egzistuoja u, v, w, x, y, kad (1) – (3) galioja. Rodome, kad visiems u, v, w, x, y (1) – (3) negalioja. Jei (1) ir (2) galioja, tada x = 0ⁿ1ⁿ2ⁿ= uvwxy su |vwx| ? n ir |vx| ? 1. (1) nurodo, kad vwx nėra 0 ir 2. Taigi arba vwx neturi 0, arba vwx neturi 2. Taigi turime apsvarstyti du atvejus. Tarkime, vwx neturi 0. Pagal (2) vx yra 1 arba 2. Taigi uwy turi „n“ 0, o uwy turi arba mažiau nei „n“ 1, arba mažiau nei „n“ 2. Tačiau (3) nurodo, kad uwy = uv⁰wx⁰y ? L. Taigi, uwy turi vienodą skaičių 0, 1 ir 2, duoda mums prieštaravimą. Atvejis, kai vwx neturi 2, yra panašus ir taip pat suteikia mums prieštaravimo. Taigi L nėra be konteksto. Šaltinis: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Įvadas į automatų teoriją, kalbas ir skaičiavimą.

Prie šio straipsnio prisidėjo Nirupamas Singhas .