Pamping lema

Pamping-lema (engl. pumping lemma) ili lema upumpavanja u teorijskoj informatici opisuje osobinu klase formalnih jezika koji nisu regularni odnosno nisu jezici sa slobodnim kontekstom.

Njeno ime potiče od engleske reči to pump, što znači pumpati. Nazvana je tako po tome što osobine jezika dokazuje procesom koji liči na pumpanje.

Razlikuje se više varijanti ove leme, u zavisnosti na koje jezike se lema primenjuje: na regiučarne ili na jezike sa slobodnim kontekstom.

Definicija

Regularni jezici

Neka je ${\mathcal {L}}_{3}$ skup regularnih jezika. Za pravljenje jednog regularnog jezika mora postojati gramatika trećeg tipa Čomskog.

Neka je L jedan regularan jezik iz ${\mathcal {L}}_{3}$. Onda postoji jedan prirodan broj n! iz N, takav da se svaka reč x iz L koju čini n ili više znakova može razložiti kao x = uvw uz sledeća pravila:

1. $\left|v\right|\geq 1$
2. $\left|uv\right|\leq n$
3. $\forall i\geq 0:uv^{i}w\in L$

Ukoliko jezik ispunjava uslove ne mora da znači da je regularan, ali svaki koji je ne ispunjava nije regularan.

Jezici sa slobodnom sintaksom

Neka je ${\mathcal {L}}_{2}$ klasa svih jezika koji se mogu opisati gramatikama drugog tipa Čomskog tj. svih jezika sa slobodnom sintaksom.

Neka je L jedan jezik sa slobodnom sintaksom, tj. jezik iz ${\mathcal {L}}_{2}$. Onda postoji konstanta n iz N takva da se sve reči z iz L mogu rastaviti kao z = uvwxy, pri čemu

1. $\left|vx\right|\geq 1$
2. $\left|vwx\right|\leq n$
3. $\forall i\geq 0:uv^{i}wx^{i}y\in L$