Er zijn twee Pumping Lemma's, die zijn gedefinieerd voor 1. Reguliere talen en 2. Context – Vrije talen Pomplemma voor reguliere talen Voor elke reguliere taal L bestaat er een geheel getal n, zodat voor alle x ? L met |x| ? n, er bestaat u, v, w ? ?^*, zodat x = uvw, en (1) |uv| ? n (2) |v| ? 1 (3) voor alles ik ? 0: uvⁱw? L In eenvoudige bewoordingen betekent dit dat als een string v wordt ‘gepompt’, d.w.z. als v een willekeurig aantal keren wordt ingevoegd, de resulterende string nog steeds in L blijft staan. Pumping Lemma wordt gebruikt als bewijs voor de onregelmatigheid van een taal. Dus als een taal regulier is, voldoet deze altijd aan het pomplemma. Als er tenminste één snaar bestaat die gemaakt is van pompen en die niet in L staat, dan is L zeker niet regulier. Het tegenovergestelde hiervan is misschien niet altijd waar. Dat wil zeggen: als het Pumping Lemma geldt, betekent dit niet dat de taal regulier is.

Laten we bijvoorbeeld L bewijzen₀₁= n? 0 is onregelmatig. Laten we aannemen dat L regulier is, dan volgen door Pumping Lemma de hierboven gegeven regels. Laten we nu x? L en |x| ? N. Dus door het Pumping Lemma bestaat er u, v, w zodat (1) – (3) gelden. We laten zien dat voor alle u, v, w, (1) – (3) niet geldt. Als (1) en (2) gelden, dan is x = 0^N1^N= uvw met |uv| ? n en |v| ? 1. Dus u = 0^A, v = 0^B, w = 0^C1^Nwaar: a+b? n, b? 1, c? 0, a + b + c = n Maar dan faalt (3) voor i = 0 uv⁰w = uw = 0^A0^C1^N= 0^{een + c}1^N? L, aangezien a + c ? N.

Pomplemma voor contextvrije talen (CFL) Het pomplemma voor CFL stelt dat het voor elke contextvrije taal L mogelijk is om twee substrings te vinden die een willekeurig aantal keren kunnen worden 'gepompt' en nog steeds in dezelfde taal zijn. Voor elke taal L verdelen we de strings in vijf delen en pompen we de tweede en vierde substring op. Pumping Lemma wordt ook hier gebruikt als hulpmiddel om te bewijzen dat een taal geen CFL is. Want als een bepaalde string niet aan de voorwaarden voldoet, is de taal geen CFL. Dus als L een CFL is, bestaat er een geheel getal n, zodat voor alle x ? L met |x| ? n, er bestaat u, v, w, x, y? ?^*, zodat x = uvwxy, en (1) |vwx| ? n (2) |vx| ? 1 (3) voor alles ik ? 0: uvⁱwxⁱEn ? l

Voor bovenstaand voorbeeld: 0^N1^Nis CFL, aangezien elke string het resultaat kan zijn van pompen op twee plaatsen, één voor 0 en de andere voor 1. Laten we bewijzen, L₀₁₂= n? 0 is niet contextvrij. Laten we aannemen dat L contextvrij is, en dan volgen door Pumping Lemma de hierboven gegeven regels. Laten we nu x? L en |x| ? N. Dus volgens het Pumping Lemma bestaan ​​er u, v, w, x, y zodat (1) – (3) gelden. We laten zien dat voor alle u, v, w, x, y (1) – (3) niet gelden. Als (1) en (2) gelden, dan is x = 0^N1^N2^N= uvwxy met |vwx| ? n en |vx| ? 1. (1) vertelt ons dat vwx niet zowel 0 als 2 bevat. Dus vwx heeft geen 0-en, of vwx heeft geen 2-en. We moeten dus twee gevallen overwegen. Stel dat vwx geen nullen heeft. Volgens (2) bevat vx een 1 of een 2. Uwy heeft dus ‘n’ 0-en en uwy heeft minder dan ‘n’ 1-en of heeft minder dan ‘n’ 2-en. Maar (3) vertelt ons dat uwy = uv⁰wx⁰jij? L. Dus, uwy heeft een gelijk aantal nullen, 1'en en 2'en, wat ons een tegenstrijdigheid geeft. Het geval waarin vwx geen 2 heeft is vergelijkbaar en geeft ons ook een tegenstrijdigheid. L is dus niet contextvrij. Bron: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2003). Inleiding tot automatentheorie, talen en berekeningen.

Dit artikel is bijgedragen door Nirupam Singh .