Existují dvě Pumping Lemmat, která jsou definována pro 1. Regulární jazyky a 2. Kontext – Volné jazyky Čerpací lemma pro běžné jazyky Pro každý regulární jazyk L existuje celé číslo n, takže pro všechna x ? L s |x| ? n, existuje u, v, w ? ?^*, takže x = uvw a (1) |uv| ? n (2) |v| ? 1 (3) pro všechny i ​​? 0: UVⁱw ? L Zjednodušeně to znamená, že pokud je řetězec v ‚pumpován‘, tj. pokud je v vloženo kolikrát, výsledný řetězec stále zůstává v L. Pumping Lemma se používá jako důkaz nepravidelnosti jazyka. Pokud je tedy jazyk regulární, vždy splňuje pumpovací lemma. Pokud existuje alespoň jedna struna vyrobená čerpáním, která není v L, pak L jistě není pravidelné. Opak toho nemusí být vždy pravdou. To znamená, že pokud platí Pumping Lemma, neznamená to, že jazyk je regulární.

Dokažme například L₀₁= n? 0 je nepravidelná. Předpokládejme, že L je regulární, pak při Pumping Lemma následují výše uvedená pravidla. Nyní, nechť x ? L a |x| ? n. Takže podle Pumping Lemma existuje u, v, w takové, že platí (1) – (3). Ukazujeme, že pro všechna u, v, w, (1) – (3) neplatí. Pokud platí (1) a (2), pak x = 0ⁿ1ⁿ= uvw s |uv| ? n a |v| ? 1. Takže u = 0^A, v = 0^b, w = 0^C1ⁿkde: a + b? n, b? 1, c? 0, a + b + c = n Ale pak (3) selže pro i = 0 uv⁰w = uw = 0^A0^C1ⁿ= 0^{a + c}1ⁿ? L, protože a + c ? n.

Pumping Lemma pro bezkontextové jazyky (CFL) Pumping Lemma pro CFL uvádí, že pro jakýkoli bezkontextový jazyk L je možné najít dva podřetězce, které lze ‚pumpovat‘ libovolněkrát a stále jsou ve stejném jazyce. Pro jakýkoli jazyk L rozdělíme jeho řetězce na pět částí a pumpujeme druhý a čtvrtý podřetězec. Pumping Lemma se zde také používá jako nástroj k prokázání, že jazyk není CFL. Protože pokud některý řetězec nesplňuje jeho podmínky, pak jazyk není CFL. Je-li tedy L CFL, existuje celé číslo n, takže pro všechna x ? L s |x| ? n, existuje u, v, w, x, y ? ?^*, takže x = uvwxy a (1) |vwx| ? n (2) |vx| ? 1 (3) pro všechny i ​​? 0: UVⁱwxⁱa ? l

Pro výše uvedený příklad 0ⁿ1ⁿje CFL, protože jakýkoli řetězec může být výsledkem pumpování na dvou místech, jedno pro 0 a druhé pro 1. Dokažme, L₀₁₂= n? 0 není bez kontextu. Předpokládejme, že L je bezkontextové, pak při Pumping Lemma následují výše uvedená pravidla. Nyní, nechť x ? L a |x| ? n. Takže podle Pumping Lemma existuje u, v, w, x, y takové, že platí (1) – (3). Ukazujeme, že pro všechna u, v, w, x, y (1) – (3) neplatí. Pokud platí (1) a (2), pak x = 0ⁿ1ⁿ2ⁿ= uvwxy s |vwx| ? na |vx| ? 1. (1) nám říká, že vwx neobsahuje jak 0, tak 2. Tedy buď vwx nemá žádné 0, nebo vwx nemá žádné 2. Musíme tedy zvážit dva případy. Předpokládejme, že vwx nemá žádné 0. Podle (2) vx obsahuje 1 nebo 2. Uwy má tedy ‚n‘ 0 a uwy má buď méně než ‚n‘ 1, nebo má méně než ‚n‘ 2. Ale (3) nám říká, že uwy = uv⁰wx⁰y ? L. Takže uwy má stejný počet 0, 1 a 2, což nám dává rozpor. Případ, kdy vwx nemá žádné 2, je podobný a také nám dává rozpor. L tedy není bezkontextové. Zdroj: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Úvod do teorie automatů, jazyků a počítání.

K tomuto článku přispěl uživatel Nirupam Singh .