On olemassa kaksi pumppauslemmaa, jotka on määritelty 1. säännöllisille kielille ja 2. kontekstille – vapaat kielet Pumppaa lemmaa tavallisille kielille Jokaiselle säännölliselle kielelle L on olemassa kokonaisluku n, joka on sellainen, että kaikilla x ? L ja |x| ? n, on olemassa u, v, w ? ?^*, siten, että x = uvw ja (1) |uv| ? n (2) |v| ? 1 (3) kaikille i ? 0: uvⁱw ? L Yksinkertaisesti sanottuna tämä tarkoittaa, että jos merkkijono v 'pumpataan', eli jos v lisätään kuinka monta kertaa tahansa, tuloksena oleva merkkijono jää silti L:ssä. Pumppauslemmaa käytetään todisteena kielen epäsäännöllisyydestä. Siten, jos kieli on säännöllinen, se täyttää aina pumppauslemman. Jos on olemassa ainakin yksi pumppauksesta tehty merkkijono, joka ei ole L:ssä, niin L ei varmasti ole säännöllinen. Tämän päinvastoin ei välttämättä aina ole totta. Eli jos Pumping Lemma pätee, se ei tarkoita, että kieli on säännöllinen.

Todistakaamme esimerkiksi L₀₁= n? 0 on epäsäännöllinen. Oletetaan, että L on säännöllinen, jolloin Pumppaamalla Lemma noudattavat yllä annetut säännöt. Anna nyt sitten x? L ja |x| ? n. Eli pumppaamalla Lemma on olemassa u, v, w, jotka (1) – (3) pätevät. Osoitamme, että kaikille u, v, w, (1) – (3) ei päde. Jos (1) ja (2) ovat voimassa, niin x = 0ⁿ1ⁿ= uvw ja |uv| ? n ja |v| ? 1. Joten u = 0^a, v = 0^b, w = 0^c1ⁿmissä: a + b? n, b? 1, c? 0, a + b + c = n Mutta silloin (3) epäonnistuu, kun i = 0 uv⁰w = uw = 0^a0^c1ⁿ= 0^{a + c}1ⁿ? L, koska a + c ? n.

Pumping Lemma kontekstittomille kielille (CFL) Pumping Lemma for CFL toteaa, että mille tahansa kontekstivapaalle kielelle L on mahdollista löytää kaksi alimerkkijonoa, jotka voidaan 'pumpata' kuinka monta kertaa tahansa ja jotka ovat silti samalla kielellä. Minkä tahansa kielen L merkkijonot jaetaan viiteen osaan ja pumpataan toinen ja neljäs osamerkkijono. Pumppaus Lemma, myös tässä, käytetään työkaluna todistamaan, että kieli ei ole CFL. Koska jos jokin merkkijono ei täytä ehtojaan, kieli ei ole CFL. Siten, jos L on CFL, on olemassa kokonaisluku n siten, että kaikilla x ? L ja |x| ? n, on olemassa u, v, w, x, y? ?^*, siten, että x = uvwxy ja (1) |vwx| ? n (2) |vx| ? 1 (3) kaikille i ? 0: uvⁱwxⁱja ? l

Yllä olevassa esimerkissä 0ⁿ1ⁿon CFL, koska mikä tahansa merkkijono voi olla tulosta pumppaamisesta kahdessa paikassa, joista toinen on 0 ja toinen 1. Todistakaamme, L₀₁₂= n? 0 ei ole kontekstiton. Oletetaan, että L on kontekstiton, jolloin Pumping Lemma noudattaa yllä annetut säännöt. Anna nyt sitten x? L ja |x| ? n. Eli pumppaamalla Lemma on olemassa u, v, w, x, y, niin että (1) – (3) pätevät. Osoitamme, että kaikille u, v, w, x, y (1) – (3) eivät päde. Jos (1) ja (2) ovat voimassa, niin x = 0ⁿ1ⁿ2ⁿ= uvwxy ja |vwx| ? n ja |vx| ? 1. (1) kertoo meille, että vwx ei sisällä sekä 0:ta että 2:ta. Siten joko vwx:ssä ei ole nollia tai vwx:ssä ei ole 2:ta. Meillä on siis kaksi tapausta harkittavana. Oletetaan, että vwx:llä ei ole nollia. Tekijän (2) mukaan vx sisältää arvon 1 tai 2. Siten uwy:ssa on 'n' nollia ja uwy:ssa on joko vähemmän kuin 'n' 1 tai vähemmän kuin n' 2. Mutta (3) kertoo meille, että uwy = uv⁰wx⁰y ? L. Joten, uwy:lla on yhtä monta nollaa, 1:tä ja 2:ta, antaa meille ristiriidan. Tapaus, jossa vwx:llä ei ole kahta, on samanlainen ja antaa meille myös ristiriidan. L ei siis ole yhteydetön. Lähde: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Johdatus automaatioteoriaan, kieliin ja laskemiseen.

Tämän artikkelin on avustanut Nirupam Singh .