Lema de pompare: Daca un limbaj L este regulat atunci exista un p0 astfel incat pentru orice w din L cu |w| >= p0 avem urmatoarele 3 reguli satisfcute:
1) w se pote scrie ca xyz cu |y| >= 1
2) |xy| <= p0
3) xy^iz apartine limbajului oricare ar fi i - asta inseamna ca putem sa il repetam pe y de oricate ori in cuvant si va ramane in limbaj

Schema de rezolvare: Lema de Pompare este folosita in momentul in care vrem sa aratam ca un Limbaj L nu este regulat. Deci vom proceda prin reducere la absurd. Presupun prin reducere la absurd ca limbajul L ar fi regulat. Atunci din lema de pompare inseamna ca exista un p0 ai sa se respecta toata conditia aia scrisa mai sus. Deci orice cuvant din w cu lungime >= p0 respecta conditia de mai sus.
Acum ce trebuie sa facem este sa alegem un cuvant care are lungime >= p0 si sa aratam ca nu poate respecta toate cele 3 conditii simultan.
Spre exemplu daca limbajul L este de forma {a^nb^n} putem sa alegem cuvantul w = a^p0b^p0 din limbaj daca are lungimea 2*p0 deci clar mai mare decat p0. Atentie: cuvantul aaabbb nu ar fi fost bun de ales pentru ca are lungime 6 si nu stim daca 6 > p0
deci cuvantul trebuie sa fie ales in functie de p0 si sa fim siguri ca lungimea lui este >= p0. In czul nostru este clar ca
a^p0b^p0 are lungime mai mare decat p0
acum regulile ne spun ca putem scrie w = a^p0b^p0 = xyz, deci il putem sparge in 3 substringuri(substringuri care respecta si conditia 2 si 3)

deci hai sa analizam ce insemna a^p0b^p0 impreuna cu regula |xy| <= p0. deoarce stim ca |xy| <= p0

este clar ca x si y sunt compuse doar din a - daca aici nu iti este clar sa ma intrebi.

dupa aca x si y sunt compuse doar din a inseamna ca putem scrie x = a^i si y = a^j(j > 0, doarece, |Y| >= 1), z va vi restul cuvantului
adica in cazul nostru a^(p0 - x - y)b^p0

acum din lema de pompare stim ca si cuvantul xyyz apartine limbajului, deci hai sa inlocuim x si y cu ce ne-a dat mai sus
si vom obtine

a^ia^ja^ja^(p0 - i - j)b^p0 = a^(p0 + j)b^p0, dar acest cuvant are mai multe a decat b si limbajul initial era de forma
L = {a^nb^n}(adica cu numar egal de a si b)

deci nu e bine, am obtinut o contradictie deci presupunerea facuta este falsa deci L nu e regulat.