Obstajata dve črpalni lemi, ki sta definirani za 1. običajne jezike in 2. kontekst – prosti jeziki Črpalna lema za navadne jezike Za vsak običajni jezik L obstaja celo število n, tako da za vse x ? L z |x| ? n, obstaja u, v, w? ?^*, tako da je x = uvw in (1) |uv| ? n (2) |v| ? 1 (3) za vse i ? 0: uv^jazw ? L Preprosto povedano, to pomeni, da če je niz v 'črpan', tj. če je v vstavljen poljubno število krat, nastali niz še vedno ostane v L. Lema o črpanju se uporablja kot dokaz za nepravilnost jezika. Torej, če je jezik pravilen, vedno izpolnjuje črpalno lemo. Če obstaja vsaj en niz, narejen iz črpanja, ki ni v L, potem L zagotovo ni regularen. Nasprotno od tega morda ni vedno res. To pomeni, da če Pumping Lemma drži, to ne pomeni, da je jezik pravilen.

Na primer, dokažimo L₀₁= n? 0 je nepravilno. Predpostavimo, da je L regularen, potem po črpalni lemi sledijo zgoraj podana pravila. Naj zdaj x ? L in |x| ? n. Torej po črpalni lemi obstajajo u, v, w takšni, da veljajo (1) – (3). Pokažemo, da za vse u, v, w (1) – (3) ne velja. Če veljata (1) in (2), potem je x = 0ⁿ1ⁿ= uvw z |uv| ? n in |v| ? 1. Torej je u = 0^a, v = 0^b, w = 0^c1ⁿkje: a + b? n, b? 1, c ? 0, a + b + c = n Toda potem (3) ne velja za i = 0 uv⁰w = uw = 0^a0^c1ⁿ= 0^{a + c}1ⁿ? L, ker a + c ? n.

Črpalna lema za jezike brez konteksta (CFL) Lema o črpanju za CFL navaja, da je za kateri koli jezik brez konteksta L mogoče najti dva podniza, ki ju je mogoče poljubno število 'črpati' in sta še vedno v istem jeziku. Za kateri koli jezik L njegove nize razdelimo na pet delov in črpamo drugi in četrti podniz. Pumping Lemma se tudi tukaj uporablja kot orodje za dokazovanje, da jezik ni CFL. Ker, če katerikoli niz ne izpolnjuje svojih pogojev, potem jezik ni CFL. Torej, če je L CFL, obstaja celo število n, tako da za vse x ? L z |x| ? n, obstaja u, v, w, x, y? ?^*, tako da je x = uvwxy in (1) |vwx| ? n (2) |vx| ? 1 (3) za vse i ? 0: uv^jazwx^jazin ? l

Za zgornji primer, 0ⁿ1ⁿje CFL, saj je vsak niz lahko rezultat črpanja na dveh mestih, enem za 0 in drugem za 1. Dokažimo, L₀₁₂= n? 0 ni brez konteksta. Predpostavimo, da je L brez konteksta, potem po črpalni lemi sledijo zgornja pravila. Naj zdaj x ? L in |x| ? n. Torej po črpalni lemi obstajajo u, v, w, x, y, tako da veljajo (1) – (3). Pokažemo, da za vse u, v, w, x, y (1) – (3) ne veljajo. Če veljata (1) in (2), potem je x = 0ⁿ1ⁿ2ⁿ= uvwxy z |vwx| ? n in |vx| ? 1. (1) nam pove, da vwx ne vsebuje 0 in 2. Tako bodisi vwx nima 0 ali pa vwx nima 2. Tako imamo dva primera za obravnavo. Recimo, da vwx nima ničel. Po (2) vx vsebuje 1 ali 2. Tako ima uwy 'n' 0, uwy pa manj kot 'n' 1 ali manj kot 'n' 2. Toda (3) nam pove, da je uwy = uv⁰wx⁰y? L. Torej ima uwy enako število 0, 1 in 2, kar nam daje protislovje. Primer, ko vwx nima dvojk, je podoben in nam daje tudi protislovje. Tako L ni brez konteksta. Vir: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Uvod v teorijo avtomatov, jezike in računalništvo.

Ta članek je prispeval Nirupam Singh .